<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>Acwing基础课 | Jixer的小屋</title><meta name="author" content="Jixer"><meta name="copyright" content="Jixer"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="基础算法快速排序AcWing 785. 快速排序1234567891011121314151617181920#include &lt;bits&#x2F;stdc++.h&gt;using namespace std;int main()&amp;#123;	vector&lt;int&gt; v;    int a;    cin &gt;&gt; a;    for(int i &#x3D; 0; i &lt; a;">
<meta property="og:type" content="article">
<meta property="og:title" content="Acwing基础课">
<meta property="og:url" content="http://www.lijunxi.site/posts/476471671/index.html">
<meta property="og:site_name" content="Jixer的小屋">
<meta property="og:description" content="基础算法快速排序AcWing 785. 快速排序1234567891011121314151617181920#include &lt;bits&#x2F;stdc++.h&gt;using namespace std;int main()&amp;#123;	vector&lt;int&gt; v;    int a;    cin &gt;&gt; a;    for(int i &#x3D; 0; i &lt; a;">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://q1.qlogo.cn/g?b=qq&nk=2770063826&s=640">
<meta property="article:published_time" content="2024-01-16T15:30:03.000Z">
<meta property="article:modified_time" content="2024-05-07T03:10:23.191Z">
<meta property="article:author" content="Jixer">
<meta property="article:tag" content="算法">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://q1.qlogo.cn/g?b=qq&nk=2770063826&s=640"><link rel="shortcut icon" href="/img/logo/favicon.ico"><link rel="canonical" href="http://www.lijunxi.site/posts/476471671/index.html"><link rel="preconnect"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css?v=4.13.0"><link rel="stylesheet" href="/pluginsSrc/@fortawesome/fontawesome-free/css/all.min.css?v=6.5.1"><link rel="stylesheet" href="/pluginsSrc/@fancyapps/ui/dist/fancybox/fancybox.css?v=5.0.33" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
  root: '/',
  algolia: undefined,
  localSearch: {"path":"/search.xml","preload":true,"top_n_per_article":1,"unescape":false,"languages":{"hits_empty":"找不到您查询的内容：${query}","hits_stats":"共找到 ${hits} 篇文章"}},
  translate: undefined,
  noticeOutdate: undefined,
  highlight: {"plugin":"highlight.js","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '',
  dateSuffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  infinitegrid: {
    js: '/pluginsSrc/@egjs/infinitegrid/dist/infinitegrid.min.js?v=4.11.1',
    buttonText: '加载更多'
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false,
  percent: {
    toc: true,
    rightside: false,
  },
  autoDarkmode: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: 'Acwing基础课',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2024-05-07 11:10:23'
}</script><script>(win=>{
      win.saveToLocal = {
        set: (key, value, ttl) => {
          if (ttl === 0) return
          const now = Date.now()
          const expiry = now + ttl * 86400000
          const item = {
            value,
            expiry
          }
          localStorage.setItem(key, JSON.stringify(item))
        },
      
        get: key => {
          const itemStr = localStorage.getItem(key)
      
          if (!itemStr) {
            return undefined
          }
          const item = JSON.parse(itemStr)
          const now = Date.now()
      
          if (now > item.expiry) {
            localStorage.removeItem(key)
            return undefined
          }
          return item.value
        }
      }
    
      win.getScript = (url, attr = {}) => new Promise((resolve, reject) => {
        const script = document.createElement('script')
        script.src = url
        script.async = true
        script.onerror = reject
        script.onload = script.onreadystatechange = function() {
          const loadState = this.readyState
          if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
          script.onload = script.onreadystatechange = null
          resolve()
        }

        Object.keys(attr).forEach(key => {
          script.setAttribute(key, attr[key])
        })

        document.head.appendChild(script)
      })
    
      win.getCSS = (url, id = false) => new Promise((resolve, reject) => {
        const link = document.createElement('link')
        link.rel = 'stylesheet'
        link.href = url
        if (id) link.id = id
        link.onerror = reject
        link.onload = link.onreadystatechange = function() {
          const loadState = this.readyState
          if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
          link.onload = link.onreadystatechange = null
          resolve()
        }
        document.head.appendChild(link)
      })
    
      win.activateDarkMode = () => {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = () => {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
        if (t === 'dark') activateDarkMode()
        else if (t === 'light') activateLightMode()
      
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
      const detectApple = () => {
        if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
          document.documentElement.classList.add('apple')
        }
      }
      detectApple()
    })(window)</script><link rel="stylesheet" href="/css/custom-all-min.css"><link rel="stylesheet" href="/css/custom-fancybox-min.css"><link rel="stylesheet" href="/css/custom-share-min.css"><meta name="generator" content="Hexo 6.3.0"></head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><script>(()=>{
  const $loadingBox = document.getElementById('loading-box')
  const $body = document.body
  const preloader = {
    endLoading: () => {
      $body.style.overflow = ''
      $loadingBox.classList.add('loaded')
    },
    initLoading: () => {
      $body.style.overflow = 'hidden'
      $loadingBox.classList.remove('loaded')
    }
  }

  preloader.initLoading()
  window.addEventListener('load',() => { preloader.endLoading() })

  if (false) {
    document.addEventListener('pjax:send', () => { preloader.initLoading() })
    document.addEventListener('pjax:complete', () => { preloader.endLoading() })
  }
})()</script><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="" data-original="https://q1.qlogo.cn/g?b=qq&amp;nk=2770063826&amp;s=640" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">52</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">19</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">7</div></a></div><hr class="custom-hr"/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-graduation-cap"></i><span> 文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/categories/"><i class="fa-fw fa fa-archive"></i><span> 分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fa fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw fa fa-folder-open"></i><span> 归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/links/"><i class="fa-fw fa fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header"><nav id="nav"><span id="blog-info"><a href="/" title="Jixer的小屋"><span class="site-name">Jixer的小屋</span></a></span><div id="menus"><div id="search-button"><a class="site-page social-icon search" href="javascript:void(0);"><i class="fas fa-search fa-fw"></i><span> 搜索</span></a></div><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 主页</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fa fa-graduation-cap"></i><span> 文章</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/categories/"><i class="fa-fw fa fa-archive"></i><span> 分类</span></a></li><li><a class="site-page child" href="/tags/"><i class="fa-fw fa fa-tags"></i><span> 标签</span></a></li><li><a class="site-page child" href="/archives/"><i class="fa-fw fa fa-folder-open"></i><span> 归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/links/"><i class="fa-fw fa fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">Acwing基础课</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2024-01-16T15:30:03.000Z" title="发表于 2024-01-16 23:30:03">2024-01-16</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2024-05-07T03:10:23.191Z" title="更新于 2024-05-07 11:10:23">2024-05-07</time></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-wordcount"><i class="far fa-file-word fa-fw post-meta-icon"></i><span class="post-meta-label">字数总计:</span><span class="word-count">8.7k</span><span class="post-meta-separator">|</span><i class="far fa-clock fa-fw post-meta-icon"></i><span class="post-meta-label">阅读时长:</span><span>48分钟</span></span><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="Acwing基础课"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h2 id="基础算法"><a href="#基础算法" class="headerlink" title="基础算法"></a>基础算法</h2><h3 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h3><h4 id="AcWing-785-快速排序"><a href="#AcWing-785-快速排序" class="headerlink" title="AcWing 785. 快速排序"></a>AcWing 785. 快速排序</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	vector&lt;int&gt; v;</span><br><span class="line">    int a;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        int m;</span><br><span class="line">        cin &gt;&gt; m;</span><br><span class="line">        v.push_back(m);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(v.begin(), v.end());</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        cout &lt;&lt; v[i] &lt;&lt; &quot; &quot;;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">  return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="第k个数"><a href="#第k个数" class="headerlink" title="第k个数"></a>第k个数</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">    vector&lt;int&gt; v;</span><br><span class="line">    int a, b;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        int m;</span><br><span class="line">        cin &gt;&gt; m;</span><br><span class="line">        v.push_back(m);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(v.begin(), v.end());</span><br><span class="line">    cout &lt;&lt; v[b-1];</span><br><span class="line"></span><br><span class="line">  return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h3><h4 id="AcWing-787-归并排序"><a href="#AcWing-787-归并排序" class="headerlink" title="AcWing 787. 归并排序"></a>AcWing 787. 归并排序</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line"></span><br><span class="line">int main()</span><br><span class="line">&#123;</span><br><span class="line">	vector&lt;int&gt; v;</span><br><span class="line">    int a;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        int m;</span><br><span class="line">        cin &gt;&gt; m;</span><br><span class="line">        v.push_back(m);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(v.begin(), v.end());</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        cout &lt;&lt; v[i] &lt;&lt; &quot; &quot;;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">  return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="二分"><a href="#二分" class="headerlink" title="二分"></a>二分</h3><p>可以直接用STL中的lower_bound和upper_bound</p>
<ul>
<li>lower_bound(n, n+a, target)</li>
<li>upper_bound(n, n+a, target)</li>
</ul>
<p><strong>举例</strong>（转载：<a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_40160605/article/details/80150252">博客链接</a>）</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">const int maxn=100000+10;</span><br><span class="line">const int INF=2*int(1e9)+10;</span><br><span class="line">#define LL long long</span><br><span class="line">int cmd(int a,int b)&#123;</span><br><span class="line">	return a&gt;b;</span><br><span class="line">&#125;</span><br><span class="line">int main()&#123;</span><br><span class="line">	int num[6]=&#123;1,2,4,7,15,34&#125;; </span><br><span class="line">	sort(num,num+6);                           //按从小到大排序 </span><br><span class="line">	int pos1=lower_bound(num,num+6,7)-num;    //返回数组中第一个大于或等于被查数的值 </span><br><span class="line">	int pos2=upper_bound(num,num+6,7)-num;    //返回数组中第一个大于被查数的值</span><br><span class="line">	cout&lt;&lt;pos1&lt;&lt;&quot; &quot;&lt;&lt;num[pos1]&lt;&lt;endl;</span><br><span class="line">	cout&lt;&lt;pos2&lt;&lt;&quot; &quot;&lt;&lt;num[pos2]&lt;&lt;endl;</span><br><span class="line">	sort(num,num+6,cmd);                      //按从大到小排序</span><br><span class="line">	int pos3=lower_bound(num,num+6,7,greater&lt;int&gt;())-num;  //返回数组中第一个小于或等于被查数的值 </span><br><span class="line">	int pos4=upper_bound(num,num+6,7,greater&lt;int&gt;())-num;  //返回数组中第一个小于被查数的值 </span><br><span class="line">	cout&lt;&lt;pos3&lt;&lt;&quot; &quot;&lt;&lt;num[pos3]&lt;&lt;endl;</span><br><span class="line">	cout&lt;&lt;pos4&lt;&lt;&quot; &quot;&lt;&lt;num[pos4]&lt;&lt;endl;</span><br><span class="line">	return 0;	</span><br><span class="line">&#125; </span><br></pre></td></tr></table></figure>

<h4 id="AcWing-789-数的范围"><a href="#AcWing-789-数的范围" class="headerlink" title="AcWing 789. 数的范围"></a>AcWing 789. 数的范围</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line">#include &lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">int n[100010];</span><br><span class="line">int a, b;</span><br><span class="line"></span><br><span class="line">// 左边距</span><br><span class="line">int get_l(int x)&#123;</span><br><span class="line">    int l = 0, r = a - 1;</span><br><span class="line">    while(l &lt; r)&#123;</span><br><span class="line">        int mid = (l + r ) / 2;</span><br><span class="line">        if(n[mid] &gt;= x) r = mid;</span><br><span class="line">        else l = mid + 1;</span><br><span class="line">    &#125;</span><br><span class="line">    return l;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">// 右边距</span><br><span class="line"> int get_r(int x)&#123;</span><br><span class="line">    int l = 0, r = a - 1;</span><br><span class="line">    while(l &lt; r)&#123;</span><br><span class="line">    	int mid = (l + r + 1) / 2;</span><br><span class="line">        if(n[mid] &lt;= x) l = mid;</span><br><span class="line">        else r = mid - 1;</span><br><span class="line">    &#125;</span><br><span class="line">    return r;</span><br><span class="line"> &#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 0; i &lt; a; i++) cin &gt;&gt; n[i];</span><br><span class="line">    for(int i = 0; i &lt; b; i++)&#123;</span><br><span class="line">        int m;</span><br><span class="line">        cin &gt;&gt; m;</span><br><span class="line">        int l = get_l(m);</span><br><span class="line">        if(n[l] != m) cout &lt;&lt; -1 &lt;&lt; &quot; &quot; &lt;&lt; -1 &lt;&lt; endl;</span><br><span class="line">		else &#123;</span><br><span class="line">			int r = get_r(m);</span><br><span class="line">			if(n[r] != m) cout &lt;&lt; -1 &lt;&lt; &quot; &quot; &lt;&lt; -1 &lt;&lt; endl;</span><br><span class="line">			else cout &lt;&lt; l &lt;&lt; &quot; &quot; &lt;&lt; r &lt;&lt; endl; </span><br><span class="line">		&#125; </span><br><span class="line">    &#125;</span><br><span class="line">	</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-790-数的三次方根"><a href="#AcWing-790-数的三次方根" class="headerlink" title="AcWing 790. 数的三次方根"></a>AcWing 790. 数的三次方根</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">double getS(double x)&#123;</span><br><span class="line">    return x * x * x;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">double fun(double x)&#123;</span><br><span class="line">    double l = -10000, r = 10000;</span><br><span class="line">    while(l &lt; r)&#123;</span><br><span class="line">        double mid = (l + r) / 2;</span><br><span class="line">        double res = getS(mid);</span><br><span class="line">        if(fabs(res - x) &lt; 0.0000000001)&#123;</span><br><span class="line">        	return mid;</span><br><span class="line">		&#125;</span><br><span class="line">        if(res &lt;= x) l = mid;</span><br><span class="line">        else r = mid;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    double a;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">	printf(&quot;%.6lf&quot;, fun(a));</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="高精度"><a href="#高精度" class="headerlink" title="高精度"></a>高精度</h3><h4 id="AcWing-791-高精度加法"><a href="#AcWing-791-高精度加法" class="headerlink" title="AcWing 791. 高精度加法"></a>AcWing 791. 高精度加法</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">a = int(input())</span><br><span class="line">b = int(input())</span><br><span class="line">print(a + b)</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-792-高精度减法"><a href="#AcWing-792-高精度减法" class="headerlink" title="AcWing 792. 高精度减法"></a>AcWing 792. 高精度减法</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">a = int(input())</span><br><span class="line">b = int(input())</span><br><span class="line">print(a - b)</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-793-高精度乘法"><a href="#AcWing-793-高精度乘法" class="headerlink" title="AcWing 793. 高精度乘法"></a>AcWing 793. 高精度乘法</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">a = int(input())</span><br><span class="line">b = int(input())</span><br><span class="line">print(a * b)</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-794-高精度除法"><a href="#AcWing-794-高精度除法" class="headerlink" title="AcWing 794. 高精度除法"></a>AcWing 794. 高精度除法</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">a = int(input())</span><br><span class="line">b = int(input())</span><br><span class="line">print(a // b)</span><br><span class="line">print(a % b)</span><br></pre></td></tr></table></figure>

<h3 id="前缀和与差分"><a href="#前缀和与差分" class="headerlink" title="前缀和与差分"></a>前缀和与差分</h3><h4 id="AcWing-795-前缀和"><a href="#AcWing-795-前缀和" class="headerlink" title="AcWing 795. 前缀和"></a>AcWing 795. 前缀和</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int n[N], m[N];</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, b;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">       cin &gt;&gt; n[i];</span><br><span class="line">       m[i] = n[i] + m[i - 1];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    while(b--)&#123;</span><br><span class="line">        int x, y;</span><br><span class="line">        cin &gt;&gt; x &gt;&gt; y;</span><br><span class="line">        cout &lt;&lt; m[y] - m[x - 1] &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-796-子矩阵的和"><a href="#AcWing-796-子矩阵的和" class="headerlink" title="AcWing 796. 子矩阵的和"></a>AcWing 796. 子矩阵的和</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int n[1001][1001], m[1001][1001];</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, b, c;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b &gt;&gt; c;</span><br><span class="line">    for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">        for(int j = 1; j &lt;= b; j++)&#123;</span><br><span class="line">            cin &gt;&gt; n[i][j];</span><br><span class="line">            m[i][j] = n[i][j] + m[i-1][j] + m[i][j-1] - m[i-1][j-1];</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while(c--)&#123;</span><br><span class="line">        int q, w, e, r;</span><br><span class="line">        cin &gt;&gt; q &gt;&gt; w &gt;&gt; e &gt;&gt; r;</span><br><span class="line">        cout &lt;&lt; m[e][r] + m[q-1][w-1] - m[q-1][r] - m[e][w-1] &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-797-差分"><a href="#AcWing-797-差分" class="headerlink" title="AcWing 797. 差分"></a>AcWing 797. 差分</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int n[N], m[N];</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">   int a, b;</span><br><span class="line">   cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">   for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">       cin &gt;&gt; n[i];</span><br><span class="line">       m[i] = n[i] - n[i-1];</span><br><span class="line">   &#125;</span><br><span class="line">   while(b--)&#123;</span><br><span class="line">       int x, y ,z;</span><br><span class="line">       cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;</span><br><span class="line">       m[x] += z;</span><br><span class="line">       m[y+1] -= z;</span><br><span class="line">   &#125;</span><br><span class="line">   for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">       n[i] = m[i] + n[i-1];</span><br><span class="line">       cout &lt;&lt; n[i] &lt;&lt; &quot; &quot;;</span><br><span class="line">   &#125;</span><br><span class="line">   </span><br><span class="line">   return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-798-差分矩阵"><a href="#AcWing-798-差分矩阵" class="headerlink" title="AcWing 798. 差分矩阵"></a>AcWing 798. 差分矩阵</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int n[1010][1010], m[1010][1010];</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">  </span><br><span class="line">   int a, b, c;</span><br><span class="line">   cin &gt;&gt; a &gt;&gt; b &gt;&gt; c;</span><br><span class="line">   for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">       for(int j = 1; j &lt;= b; j++)&#123;</span><br><span class="line">           cin &gt;&gt; n[i][j];</span><br><span class="line">           m[i][j] = n[i][j] - n[i-1][j] - n[i][j-1] + n[i-1][j-1];</span><br><span class="line">       &#125;</span><br><span class="line">   &#125;</span><br><span class="line">   while(c--)&#123;</span><br><span class="line">       int q, w, e, r, t;</span><br><span class="line">       cin &gt;&gt; q &gt;&gt; w &gt;&gt; e &gt;&gt; r &gt;&gt; t;</span><br><span class="line">       m[q][w] += t;</span><br><span class="line">       m[e+1][r+1] += t;</span><br><span class="line">       m[e+1][w] -= t;</span><br><span class="line">       m[q][r+1] -= t;</span><br><span class="line">   &#125;</span><br><span class="line">  for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">      for(int j = 1; j &lt;= b; j++)&#123;</span><br><span class="line">          n[i][j] = n[i-1][j] + n[i][j-1] - n[i-1][j-1] + m[i][j];</span><br><span class="line">          cout &lt;&lt; n[i][j] &lt;&lt; &quot; &quot;;</span><br><span class="line">      &#125;</span><br><span class="line">      cout &lt;&lt; endl;</span><br><span class="line">  &#125;</span><br><span class="line">   </span><br><span class="line">   return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="双指针算法"><a href="#双指针算法" class="headerlink" title="双指针算法"></a>双指针算法</h3><h4 id="AcWing-799-最长连续不重复子序列"><a href="#AcWing-799-最长连续不重复子序列" class="headerlink" title="AcWing 799. 最长连续不重复子序列"></a>AcWing 799. 最长连续不重复子序列</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int n[N];</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, l, r, res = 0;</span><br><span class="line">    map&lt;int, int&gt; is;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    for(int i = 0, j = 0; i &lt; a; i++)&#123;</span><br><span class="line">        cin &gt;&gt; n[i];</span><br><span class="line">        is[n[i]] ++;</span><br><span class="line">        while(is[n[i]] &gt; 1)&#123;</span><br><span class="line">            is[n[j]] --;</span><br><span class="line">            j ++;</span><br><span class="line">        &#125;</span><br><span class="line">        res = max(res, i - j + 1);</span><br><span class="line">    &#125;</span><br><span class="line">    cout &lt;&lt; res &lt;&lt; endl;</span><br><span class="line">  </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-800-数组元素的目标和"><a href="#AcWing-800-数组元素的目标和" class="headerlink" title="AcWing 800. 数组元素的目标和"></a>AcWing 800. 数组元素的目标和</h4><p>哈希方法</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int n[N], m[N];</span><br><span class="line">unordered_map&lt;int, int&gt; ump;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, b, c, r1 = 0, r2 = 0;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b &gt;&gt; c;</span><br><span class="line">    for(int i = 0; i &lt; a; i++) &#123;</span><br><span class="line">        cin &gt;&gt; n[i];</span><br><span class="line">        ump[n[i]] = i;</span><br><span class="line">    &#125;</span><br><span class="line">    for(int j = 0; j &lt; b; j++) &#123;</span><br><span class="line">        cin &gt;&gt; m[j];</span><br><span class="line">        if(ump.count(c - m[j]))&#123;</span><br><span class="line">            r1 = ump[c - m[j]], r2 = j;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    cout &lt;&lt; r1 &lt;&lt; &quot; &quot; &lt;&lt; r2 &lt;&lt; endl;</span><br><span class="line">  </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-2816-判断子序列"><a href="#AcWing-2816-判断子序列" class="headerlink" title="AcWing 2816. 判断子序列"></a>AcWing 2816. 判断子序列</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int n[N], m[N];</span><br><span class="line">unordered_map&lt;int, int&gt; ump;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, b;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 0; i &lt; a; i++) cin &gt;&gt; n[i];</span><br><span class="line">    for(int j = 0; j &lt; b; j++) cin &gt;&gt; m[j];</span><br><span class="line">   </span><br><span class="line">    int x = 0, y = 0;</span><br><span class="line">    while(x &lt; a &amp;&amp; y &lt; b)&#123;</span><br><span class="line">        if(n[x] == m[y]) x ++;</span><br><span class="line">        y ++;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    if(x == a) cout &lt;&lt; &quot;Yes&quot; &lt;&lt; endl;</span><br><span class="line">    else cout &lt;&lt; &quot;No&quot; &lt;&lt; endl;</span><br><span class="line">  </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="位运算"><a href="#位运算" class="headerlink" title="位运算"></a>位运算</h3><h4 id="AcWing-801-二进制中1的个数"><a href="#AcWing-801-二进制中1的个数" class="headerlink" title="AcWing 801. 二进制中1的个数"></a>AcWing 801. 二进制中1的个数</h4><blockquote>
<p>小知识：n的二进制表示中第k位是几？<br>答案：n &gt;&gt; k &amp; 1<br>n右移k位&amp;1后得出二进制数的最后一位</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">// 返回x的最后一位1</span><br><span class="line">// 比如10010的最后一位就是10</span><br><span class="line">int lowbit(int x)&#123;</span><br><span class="line">    return x &amp; -x;    </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">        </span><br><span class="line">    int a, b, res;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        cin &gt;&gt; b;</span><br><span class="line">        res = 0;</span><br><span class="line">        while(b)&#123;</span><br><span class="line">            b -= lowbit(b);</span><br><span class="line">            res ++;</span><br><span class="line">        &#125;</span><br><span class="line">        cout &lt;&lt; res &lt;&lt; &quot; &quot;;</span><br><span class="line">    &#125;</span><br><span class="line">        </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="离散化"><a href="#离散化" class="headerlink" title="离散化"></a>离散化</h3><h4 id="AcWing-802-区间和"><a href="#AcWing-802-区间和" class="headerlink" title="AcWing 802. 区间和"></a>AcWing 802. 区间和</h4><blockquote>
<p>小知识<br>离散化：将100，2000，30000，4000000映射为1，2，3，4的过程</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">// 此处不是1e5+10</span><br><span class="line">// 极端情况下第一排输入会有1e5的数据，第二排会有2e5的数据</span><br><span class="line">const int N = 3e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int s[N], f[N];</span><br><span class="line"></span><br><span class="line">vector&lt;int&gt; v;</span><br><span class="line">vector&lt;pair&lt;int, int&gt; &gt; q, w;</span><br><span class="line">// 二分查找元素下标</span><br><span class="line">int find(int x)&#123;</span><br><span class="line">    int l = 0, r = v.size() - 1;</span><br><span class="line">    while(l &lt; r)&#123;</span><br><span class="line">        int mid = l + r &gt;&gt; 1;</span><br><span class="line">        if(v[mid] &gt;= x) r = mid;</span><br><span class="line">        else l = mid + 1;</span><br><span class="line">    &#125;</span><br><span class="line">    return l + 1;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, b, m, n;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        cin &gt;&gt; m &gt;&gt; n;</span><br><span class="line">        q.push_back(&#123;m, n&#125;);</span><br><span class="line">        v.push_back(m);</span><br><span class="line">    &#125;</span><br><span class="line">    for(int j = 0; j &lt; b; j++)&#123;</span><br><span class="line">        cin &gt;&gt; m &gt;&gt; n;</span><br><span class="line">        w.push_back(&#123;m, n&#125;);</span><br><span class="line">        v.push_back(m);</span><br><span class="line">        v.push_back(n);</span><br><span class="line">    &#125;</span><br><span class="line">    sort(v.begin(), v.end());</span><br><span class="line">    // 去重</span><br><span class="line">    v.erase(unique(v.begin(), v.end()), v.end());</span><br><span class="line">    // 离散化处理</span><br><span class="line">    for(auto i: q)&#123;</span><br><span class="line">        int x = find(i.first);</span><br><span class="line">        s[x] += i.second;</span><br><span class="line">    &#125;</span><br><span class="line">    // 预处理前缀和</span><br><span class="line">    for(int i = 1; i &lt;= v.size(); i++)&#123;</span><br><span class="line">        f[i] = f[i-1] + s[i];</span><br><span class="line">    &#125;</span><br><span class="line">    // 查询结果</span><br><span class="line">    for(auto i: w)&#123;</span><br><span class="line">        int l = find(i.first), r = find(i.second);</span><br><span class="line">        cout &lt;&lt; f[r] - f[l-1] &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><img src="" data-original="http://www.lijunxi.site:4000/api/file/download/6261dfbb-afd5-42b9-bcdf-46091f5b8e0f.jpg" alt="图片描述"></p>
<p>数据范围分析</p>
<h3 id="区间合并"><a href="#区间合并" class="headerlink" title="区间合并"></a>区间合并</h3><h4 id="AcWing-803-区间合并"><a href="#AcWing-803-区间合并" class="headerlink" title="AcWing 803. 区间合并"></a>AcWing 803. 区间合并</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ; </span><br><span class="line"></span><br><span class="line">struct point&#123;</span><br><span class="line">    int x, y;</span><br><span class="line">&#125; n[N];</span><br><span class="line"></span><br><span class="line">bool cmp(point a, point b)&#123;</span><br><span class="line">    if(a.x == b.x) return a.y &lt; b.y;</span><br><span class="line">    return a.x &lt; b.x;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, idx = 0;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    for(int i = 0; i &lt; a; i++) cin &gt;&gt; n[i].x &gt;&gt; n[i].y;</span><br><span class="line">    sort(n, n+a, cmp);</span><br><span class="line">    int langm = n[0].y;</span><br><span class="line">    for(int i = 1; i &lt; a; i++)&#123;</span><br><span class="line">        langm = max(langm, n[i-1].y);</span><br><span class="line">        if(langm &lt; n[i].x) idx++;</span><br><span class="line">    &#125;</span><br><span class="line">    cout &lt;&lt; idx + 1 &lt;&lt; endl;</span><br><span class="line">  </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="数据结构"><a href="#数据结构" class="headerlink" title="数据结构"></a>数据结构</h2><h3 id="单链表"><a href="#单链表" class="headerlink" title="单链表"></a>单链表</h3><h4 id="AcWing-826-单链表"><a href="#AcWing-826-单链表" class="headerlink" title="AcWing 826. 单链表"></a>AcWing 826. 单链表</h4><p>数组模拟单链表</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line"></span><br><span class="line">// 头指针（用下表指针辅助），下标指针</span><br><span class="line">int hidx = -1, idx = 0;</span><br><span class="line">// 元素值，元素下表</span><br><span class="line">int n[N], ne[N];</span><br><span class="line"></span><br><span class="line">void insert(int k, int x)&#123;</span><br><span class="line">    // 新节点值赋值</span><br><span class="line">    n[idx] = x;</span><br><span class="line">    // 将新结点下一个结点赋值为插入位置的下一个结点</span><br><span class="line">    ne[idx] = ne[k];</span><br><span class="line">    // 将插入位置的一下个节点指向新节点</span><br><span class="line">    ne[k] = idx;</span><br><span class="line">    idx++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void addHead(int x)&#123;</span><br><span class="line">    // 头节点赋值</span><br><span class="line">    n[idx] = x;</span><br><span class="line">    // 指向头指针</span><br><span class="line">    ne[idx] = hidx;</span><br><span class="line">    // 更改头指针为当前下表</span><br><span class="line">    hidx = idx;</span><br><span class="line">    idx++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void del(int idx)&#123;</span><br><span class="line">    ne[idx] = ne[ne[idx]];   </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int x, k, num; </span><br><span class="line">    char s;</span><br><span class="line">    cin &gt;&gt; x;</span><br><span class="line">    while(x--)&#123;</span><br><span class="line">        cin &gt;&gt; s;</span><br><span class="line">        if(s == &#x27;H&#x27;)&#123;</span><br><span class="line">            cin &gt;&gt; num;</span><br><span class="line">            addHead(num);</span><br><span class="line">        &#125;</span><br><span class="line">        else if(s == &#x27;D&#x27;)&#123;</span><br><span class="line">            cin &gt;&gt; k;</span><br><span class="line">            //判断是否删除的为头节点</span><br><span class="line">            if(!k) hidx = ne[hidx];  </span><br><span class="line">            del(k-1);</span><br><span class="line">        &#125;</span><br><span class="line">        else&#123;</span><br><span class="line">            cin &gt;&gt; k &gt;&gt; num;</span><br><span class="line">            insert(k-1, num);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while(hidx != -1)&#123;</span><br><span class="line">        cout &lt;&lt; n[hidx] &lt;&lt; &quot; &quot;;</span><br><span class="line">        hidx = ne[hidx];</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="双链表"><a href="#双链表" class="headerlink" title="双链表"></a>双链表</h3><h3 id="栈"><a href="#栈" class="headerlink" title="栈"></a>栈</h3><h4 id="AcAcWing-3302-表达式求值"><a href="#AcAcWing-3302-表达式求值" class="headerlink" title="AcAcWing 3302. 表达式求值"></a>AcAcWing 3302. 表达式求值</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line"></span><br><span class="line">stack&lt;int&gt; s;</span><br><span class="line">stack&lt;char&gt; f;</span><br><span class="line">unordered_map&lt;char, int&gt; ump;</span><br><span class="line"></span><br><span class="line">void init_map()&#123;</span><br><span class="line">	ump[&#x27;*&#x27;] = 2;</span><br><span class="line">	ump[&#x27;/&#x27;] = 2;</span><br><span class="line">	ump[&#x27;+&#x27;] = 1;</span><br><span class="line">	ump[&#x27;-&#x27;] = 1;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void eval()&#123;</span><br><span class="line">	int num = 0;</span><br><span class="line">	int x = s.top(); s.pop();</span><br><span class="line">	int y = s.top(); s.pop();</span><br><span class="line">	char op = f.top(); f.pop();</span><br><span class="line">	if(op == &#x27;+&#x27;) num = x + y;</span><br><span class="line">	else if(op == &#x27;-&#x27;) num = y - x;</span><br><span class="line">	else if(op == &#x27;*&#x27;) num = x * y;</span><br><span class="line">	else num = y / x;</span><br><span class="line">	s.push(num);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    init_map();</span><br><span class="line">    string str;</span><br><span class="line">    int num, idx = 0;</span><br><span class="line">    char c;</span><br><span class="line">    cin &gt;&gt; str;</span><br><span class="line">    int len = str.size();</span><br><span class="line">    for(int i = 0; i &lt; len; i++)&#123;</span><br><span class="line">        if(str[i] &gt;= &#x27;0&#x27; &amp;&amp; str[i] &lt;= &#x27;9&#x27;)&#123;</span><br><span class="line">            idx = i;</span><br><span class="line">            num = 0;</span><br><span class="line">            while(str[idx] &gt;= &#x27;0&#x27; &amp;&amp; str[idx] &lt;= &#x27;9&#x27; &amp;&amp; idx &lt; len)&#123;</span><br><span class="line">                num = num * 10 + str[idx] - &#x27;0&#x27;;</span><br><span class="line">                idx++; </span><br><span class="line">            &#125;</span><br><span class="line">            s.push(num);</span><br><span class="line">            i = idx - 1;</span><br><span class="line">        &#125;</span><br><span class="line">        else if(str[i] == &#x27;(&#x27;) f.push(str[i]);</span><br><span class="line">        else if(str[i] == &#x27;)&#x27;)&#123;</span><br><span class="line">       		while(f.size() &amp;&amp; s.size() &gt;= 2 &amp;&amp; ump[str[i]] &lt;= ump[f.top()] &amp;&amp; f.top() != &#x27;(&#x27;) eval();</span><br><span class="line">       		f.pop();</span><br><span class="line">        &#125;</span><br><span class="line">        else&#123;</span><br><span class="line">        	while(f.size() &amp;&amp; s.size() &gt;= 2 &amp;&amp; ump[str[i]] &lt;= ump[f.top()]) eval();</span><br><span class="line">            f.push(str[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    while(f.size()) eval();</span><br><span class="line">	cout &lt;&lt; s.top() &lt;&lt; endl; </span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="队列"><a href="#队列" class="headerlink" title="队列"></a>队列</h3><h4 id="AcWing-829-模拟队列"><a href="#AcWing-829-模拟队列" class="headerlink" title="AcWing 829. 模拟队列"></a>AcWing 829. 模拟队列</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line">queue&lt;int&gt; q;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    int a, num;</span><br><span class="line">    string s;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    while(a--)&#123;</span><br><span class="line">        cin &gt;&gt; s;</span><br><span class="line">        if(s == &quot;push&quot;)&#123;</span><br><span class="line">            cin &gt;&gt; num;</span><br><span class="line">            q.push(num);</span><br><span class="line">        &#125;</span><br><span class="line">        else if(s == &quot;pop&quot;)&#123;</span><br><span class="line">            q.pop();</span><br><span class="line">        &#125;</span><br><span class="line">        else if(s == &quot;empty&quot;)&#123;</span><br><span class="line">            if(q.empty()) cout &lt;&lt;&quot;YES&quot;&lt;&lt;endl;</span><br><span class="line">            else cout &lt;&lt;&quot;NO&quot; &lt;&lt; endl;</span><br><span class="line">        &#125;</span><br><span class="line">        else&#123;</span><br><span class="line">            cout &lt;&lt; q.front() &lt;&lt; endl;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">   </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="单调栈"><a href="#单调栈" class="headerlink" title="单调栈"></a>单调栈</h3><h4 id="AcWing-830-单调栈"><a href="#AcWing-830-单调栈" class="headerlink" title="AcWing 830. 单调栈"></a>AcWing 830. 单调栈</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">stack&lt;int&gt; s;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, num;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    for(int i = 0; i &lt; a; i++) &#123;</span><br><span class="line">        cin &gt;&gt; num;</span><br><span class="line">        while(s.size() &amp;&amp; s.top() &gt;= num) s.pop();</span><br><span class="line">        if(!s.size()) cout &lt;&lt; -1 &lt;&lt; &quot; &quot;;</span><br><span class="line">        else cout &lt;&lt; s.top() &lt;&lt; &quot; &quot;;</span><br><span class="line">        s.push(num);</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="单调队列"><a href="#单调队列" class="headerlink" title="单调队列"></a>单调队列</h3><h4 id="AcWing-154-滑动窗口"><a href="#AcWing-154-滑动窗口" class="headerlink" title="AcWing 154. 滑动窗口"></a>AcWing 154. 滑动窗口</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;algorithm&gt;</span><br><span class="line">#include&lt;deque&gt;</span><br><span class="line">#include&lt;vector&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e6 + 10 ;</span><br><span class="line"></span><br><span class="line">// deque没法直接获取下表的元素值，所以需要用一个数组来维护 </span><br><span class="line">int n[N];</span><br><span class="line">deque&lt;int&gt; dq; </span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">  </span><br><span class="line">    int a, b, num;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 1; i &lt;= a; i++) cin &gt;&gt; n[i];</span><br><span class="line">    for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">    	// 当尾元素比n[i]大时，需要弹出 </span><br><span class="line">    	while(dq.size() &amp;&amp; n[dq.back()] &gt; n[i]) dq.pop_back();</span><br><span class="line">    	dq.push_back(i);</span><br><span class="line">    	// 当队列的个数满足b时们需要弹出首元素</span><br><span class="line">		// 这里不能用dq.size()来判断是否满足个数，因为可能出现首元素到i之间有些元素已经弹出了但size总数任然小于b情况 </span><br><span class="line">    	if(dq.size() &amp;&amp; i - dq.front() &gt;= b) dq.pop_front();</span><br><span class="line">    	// 当i大于b时候就能开始输出了，这里也不能用dq.size()来判断，因为存在整个过程都小于b的情况，这样就没有输出了 </span><br><span class="line">		if(i &gt;= b) cout &lt;&lt; n[dq.front()] &lt;&lt; &quot; &quot;;</span><br><span class="line">	&#125;</span><br><span class="line">	dq.clear();</span><br><span class="line">	puts(&quot;&quot;);</span><br><span class="line">      for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">    	while(dq.size() &amp;&amp; n[dq.back()] &lt; n[i]) dq.pop_back();</span><br><span class="line">    	dq.push_back(i);</span><br><span class="line">    	if(dq.size() &amp;&amp; i - dq.front() &gt;= b) dq.pop_front();</span><br><span class="line">		if(i &gt;= b) cout &lt;&lt; n[dq.front()] &lt;&lt; &quot; &quot;;</span><br><span class="line">	&#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="KMP"><a href="#KMP" class="headerlink" title="KMP"></a>KMP</h3><h3 id="Tire"><a href="#Tire" class="headerlink" title="Tire"></a>Tire</h3><h4 id="AcWing-835-Trie字符串统计"><a href="#AcWing-835-Trie字符串统计" class="headerlink" title="AcWing 835. Trie字符串统计"></a>AcWing 835. Trie字符串统计</h4><blockquote>
<p>Trie树（字典树）：高效存储和查找字符串集合的数据结合</p>
</blockquote>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;algorithm&gt;</span><br><span class="line">#include&lt;deque&gt;</span><br><span class="line">#include&lt;vector&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line"></span><br><span class="line">// son[][]存储子节点的位置，分支最多26条</span><br><span class="line">// cnt[]存储以某节点结尾的字符串个数（同时也起标记作用）</span><br><span class="line">// idx表示当前要插入的节点是第几个,每创建一个节点值+1</span><br><span class="line">int son[N][26], cnt[N], idx = 0;</span><br><span class="line"></span><br><span class="line">void insert(string str)&#123;</span><br><span class="line">	// 类似指针，指向当前节点</span><br><span class="line">	int p = 0;</span><br><span class="line">	for(int i = 0; i &lt; str.size(); i++)&#123;</span><br><span class="line">		int s = str[i] - &#x27;a&#x27;;</span><br><span class="line">		// 该字符不存在就创建一个 </span><br><span class="line">		if(!son[p][s]) son[p][s] = ++idx;</span><br><span class="line">		// 	p指向下一个节点</span><br><span class="line">		p = son[p][s];</span><br><span class="line">	&#125;</span><br><span class="line">	// 统计字符串个数 </span><br><span class="line">	cnt[p] ++;</span><br><span class="line">&#125; </span><br><span class="line"></span><br><span class="line">int query(string str)&#123;</span><br><span class="line">	int p = 0;</span><br><span class="line">	for(int i = 0; i &lt; str.size(); i++)&#123;</span><br><span class="line">		int s = str[i] - &#x27;a&#x27;;</span><br><span class="line">		if(!son[p][s]) return 0;</span><br><span class="line">		p = son[p][s]; </span><br><span class="line">	&#125;</span><br><span class="line">	return cnt[p];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line"> </span><br><span class="line">	int a;</span><br><span class="line">	char c;</span><br><span class="line">	string str;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	while(a--)&#123;</span><br><span class="line">		cin &gt;&gt; c;</span><br><span class="line">		cin &gt;&gt; str;</span><br><span class="line">		if(c == &#x27;I&#x27;) insert(str);</span><br><span class="line">		else cout &lt;&lt; query(str) &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-143-最大异或对"><a href="#AcWing-143-最大异或对" class="headerlink" title="AcWing 143. 最大异或对"></a>AcWing 143. 最大异或对</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;algorithm&gt;</span><br><span class="line">#include&lt;deque&gt;</span><br><span class="line">#include&lt;vector&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">// 最多有1e5个数，每个数的二进制数有31位，极限情况下就1e5 * 31</span><br><span class="line">const int N = 31e5 + 10 ;</span><br><span class="line"></span><br><span class="line">int son[N][2], n[N], idx = 0;</span><br><span class="line"></span><br><span class="line">// 将数字插入trie树中 </span><br><span class="line">void insert(int x)&#123;</span><br><span class="line">	int p = 0;</span><br><span class="line">	// 数的范围为小于2e31次方 </span><br><span class="line">	for(int i = 30; i &gt;= 0; i --)&#123;</span><br><span class="line">		int s = x &gt;&gt; i &amp; 1;</span><br><span class="line">		if(!son[p][s]) son[p][s] = ++idx;</span><br><span class="line">		p = son[p][s];</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int query(int x)&#123;</span><br><span class="line">	int p = 0, res = 0;</span><br><span class="line">	for(int i = 30; i &gt;= 0; i--)&#123;</span><br><span class="line">		// x二进制第i位上的数 </span><br><span class="line">		int s = x &gt;&gt; i &amp; 1;</span><br><span class="line">		// 若存在相反的数 </span><br><span class="line">		if(son[p][!s])&#123;</span><br><span class="line">			p = son[p][!s];</span><br><span class="line">			// 1左移i位就是2^(30-i)次方 </span><br><span class="line">			res += 1 &lt;&lt; i;</span><br><span class="line">		&#125;</span><br><span class="line">		else&#123;</span><br><span class="line">			p = son[p][s];</span><br><span class="line">			res += 0 &lt;&lt; i;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return res;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line"></span><br><span class="line">	int a, res = 0;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	for(int i = 0; i &lt; a; i++) &#123;</span><br><span class="line">		cin &gt;&gt; n[i];</span><br><span class="line">		insert(n[i]);</span><br><span class="line">	&#125;</span><br><span class="line">	for(int i = 0; i &lt; a; i++) res = max(res, query(n[i]));</span><br><span class="line">	cout &lt;&lt; res &lt;&lt; endl;</span><br><span class="line">	</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="并查集"><a href="#并查集" class="headerlink" title="并查集"></a>并查集</h3><h4 id="AcWing-836-合并集合"><a href="#AcWing-836-合并集合" class="headerlink" title="AcWing 836. 合并集合"></a>AcWing 836. 合并集合</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;iostream&gt;</span><br><span class="line">#include&lt;algorithm&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10 ;</span><br><span class="line">int n[N];</span><br><span class="line"></span><br><span class="line">// 找到祖宗结点</span><br><span class="line">int find(int x)&#123;</span><br><span class="line">    // 修改结点，避免重复查找</span><br><span class="line">   if(n[x] != x) n[x] = find(n[x]);</span><br><span class="line">   return n[x];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    int a, b;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 0; i &lt; a; i++) n[i] = i;</span><br><span class="line">    for(int i = 0; i &lt; b; i++)&#123;</span><br><span class="line">        char x;</span><br><span class="line">        int o, p;</span><br><span class="line">        cin &gt;&gt; x &gt;&gt; o &gt;&gt; p;</span><br><span class="line">        if(x == &#x27;M&#x27;)&#123;</span><br><span class="line">            n[find(o)] = find(p);</span><br><span class="line">        &#125;</span><br><span class="line">        else&#123;</span><br><span class="line">            if(find(o) == find(p)) cout &lt;&lt; &quot;Yes&quot; &lt;&lt; endl;</span><br><span class="line">            else cout &lt;&lt; &quot;No&quot; &lt;&lt; endl;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">     </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="堆"><a href="#堆" class="headerlink" title="堆"></a>堆</h3><blockquote>
<p>堆：优先队列</p>
</blockquote>
<h4 id="AcWing-838-堆排序"><a href="#AcWing-838-堆排序" class="headerlink" title="AcWing 838. 堆排序"></a>AcWing 838. 堆排序</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line">int n[N];</span><br><span class="line">// 从小到大排序，从大到小就为less&lt;int&gt;，与sort相反</span><br><span class="line">priority_queue&lt;int, vector&lt;int&gt;, greater&lt;int&gt;&gt; pq;</span><br><span class="line">int main()&#123;</span><br><span class="line">    </span><br><span class="line">    int a, b, num;</span><br><span class="line">    cin&gt;&gt; a &gt;&gt; b;</span><br><span class="line">    for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">        cin &gt;&gt; num;</span><br><span class="line">        pq.push(num);</span><br><span class="line">    &#125;</span><br><span class="line">    int idx = 0;</span><br><span class="line">    while(idx != b)&#123;</span><br><span class="line">        idx ++;</span><br><span class="line">        cout &lt;&lt; pq.top() &lt;&lt; &quot; &quot;;</span><br><span class="line">        pq.pop();</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="哈希表"><a href="#哈希表" class="headerlink" title="哈希表"></a>哈希表</h3><h2 id="搜索与图论"><a href="#搜索与图论" class="headerlink" title="搜索与图论"></a>搜索与图论</h2><h3 id="DFS"><a href="#DFS" class="headerlink" title="DFS"></a>DFS</h3><h4 id="AcWing-842-排列数字"><a href="#AcWing-842-排列数字" class="headerlink" title="AcWing 842. 排列数字"></a>AcWing 842. 排列数字</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line">    </span><br><span class="line">int a;</span><br><span class="line">int is[N];</span><br><span class="line">vector&lt;int&gt; v;</span><br><span class="line"></span><br><span class="line">void dfs(int x)&#123;</span><br><span class="line">    if(x == 0) return; </span><br><span class="line">    if(v.size() == a)&#123;</span><br><span class="line">    	for(int i = 0; i &lt; a; i++) cout &lt;&lt; v[i] &lt;&lt; &quot; &quot;;</span><br><span class="line">    	cout &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">	for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">		if(!is[i])&#123;</span><br><span class="line">			is[i] = 1;</span><br><span class="line">			v.push_back(i);</span><br><span class="line">			dfs(i);</span><br><span class="line">			v.pop_back();</span><br><span class="line">			is[i] = 0;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    dfs(a);</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-843-n-皇后问题"><a href="#AcWing-843-n-皇后问题" class="headerlink" title="AcWing 843. n-皇后问题"></a>AcWing 843. n-皇后问题</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line">    </span><br><span class="line">int a;</span><br><span class="line">char n[11][11];</span><br><span class="line">int l[11], xie[11], fx[11];</span><br><span class="line"></span><br><span class="line">void print()&#123;</span><br><span class="line">	for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">		for(int j = 1; j &lt;= a; j++)&#123;</span><br><span class="line">			cout &lt;&lt; n[i][j];</span><br><span class="line">		&#125;</span><br><span class="line">		puts(&quot;&quot;);</span><br><span class="line">	&#125;</span><br><span class="line">	puts(&quot;&quot;);</span><br><span class="line">&#125; </span><br><span class="line"></span><br><span class="line">void dfs(int x)&#123;</span><br><span class="line">	if(x == a + 1)&#123;</span><br><span class="line">		print();</span><br><span class="line">		return;</span><br><span class="line">	&#125;</span><br><span class="line">    for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">    	// 	i - x + a是为了避免出现下标是负数的情况 </span><br><span class="line">    	if(!l[i] &amp;&amp; !xie[i - x + a] &amp;&amp; !fx[i + x])&#123;</span><br><span class="line">    		n[x][i] = &#x27;Q&#x27;;</span><br><span class="line">    		xie[i - x + a] = 1;</span><br><span class="line">    		fx[i + x] = 1;</span><br><span class="line">    		l[i] = 1;</span><br><span class="line">    		dfs(x + 1);</span><br><span class="line">    		n[x][i] = &#x27;.&#x27;;</span><br><span class="line">    		xie[i - x + a] = 0;</span><br><span class="line">    		fx[i + x] = 0;</span><br><span class="line">    		l[i] = 0;</span><br><span class="line">		&#125;</span><br><span class="line">	</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">  	</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">		for(int j = 1; j &lt;= a; j++)&#123;</span><br><span class="line">			n[i][j] = &#x27;.&#x27;;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">    dfs(1);</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="BFS"><a href="#BFS" class="headerlink" title="BFS"></a>BFS</h3><h4 id="AcWing-844-走迷宫"><a href="#AcWing-844-走迷宫" class="headerlink" title="AcWing 844. 走迷宫"></a>AcWing 844. 走迷宫</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line"></span><br><span class="line">int a, b;</span><br><span class="line">int n[1010][1010], is[1001][1001];</span><br><span class="line">int ix[4] = &#123;1, -1, 0 ,0&#125;, iy[4] = &#123;0, 0, 1, -1&#125;;</span><br><span class="line"></span><br><span class="line">void bfs(int x, int y)&#123;</span><br><span class="line">    queue&lt;pair&lt;int, int&gt;&gt; q;</span><br><span class="line">    map&lt;pair&lt;int, int&gt;, int&gt; mp;</span><br><span class="line">    q.push(&#123;0, 0&#125;);</span><br><span class="line">    mp[&#123;0, 0&#125;] = 0;</span><br><span class="line">    while(!q.empty())&#123;</span><br><span class="line">    	auto top = q.front();</span><br><span class="line">    	q.pop();</span><br><span class="line">    	int xx = top.first, yy = top.second;</span><br><span class="line">    	if(xx == a - 1 &amp;&amp; yy == b - 1)&#123;</span><br><span class="line">    		cout &lt;&lt; mp[&#123;xx, yy&#125;] &lt;&lt; endl;</span><br><span class="line">    		return;</span><br><span class="line">		&#125;</span><br><span class="line">		for(int i = 0; i &lt; 4; i++)&#123;</span><br><span class="line">			int x = xx + ix[i], y = yy + iy[i];</span><br><span class="line">			if(!n[x][y] &amp;&amp; !is[x][y] &amp;&amp; x &gt;= 0 &amp;&amp; x &lt; a &amp;&amp; y &gt;= 0 &amp;&amp; y &lt; b)&#123;</span><br><span class="line">				is[x][y] = 1;</span><br><span class="line">				q.push(&#123;x, y&#125;);</span><br><span class="line">				mp[&#123;x, y&#125;] = mp[&#123;xx, yy&#125;] + 1;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">  	</span><br><span class="line">	cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">	for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">	    for(int j = 0; j &lt; b; j++)&#123;</span><br><span class="line">	        cin &gt;&gt; n[i][j];</span><br><span class="line">	    &#125;</span><br><span class="line">	&#125;</span><br><span class="line">	bfs(0, 0);</span><br><span class="line">    </span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="树与图的深度优先遍历"><a href="#树与图的深度优先遍历" class="headerlink" title="树与图的深度优先遍历"></a>树与图的深度优先遍历</h3><h4 id="AcWing-846-树的重心"><a href="#AcWing-846-树的重心" class="headerlink" title="AcWing 846. 树的重心"></a>AcWing 846. 树的重心</h4><p>图的存储采用数组模拟邻接表</p>
<p>思路：邻接表dfs</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 2e5 + 10;</span><br><span class="line"></span><br><span class="line">// 邻接表头结点 </span><br><span class="line">int h[N];</span><br><span class="line">// 存储元素 </span><br><span class="line">int e[N];</span><br><span class="line">// 下个节点值</span><br><span class="line">int ne[N];</span><br><span class="line">// 结点是否访问过</span><br><span class="line">int st[N]; </span><br><span class="line">// 单链表指针 </span><br><span class="line">int idx = 0; </span><br><span class="line">int a, ans = N; </span><br><span class="line"></span><br><span class="line">void add(int x, int y)&#123;</span><br><span class="line">	e[idx] = y, ne[idx] = h[x], h[x] = idx++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int dfs(int x)&#123;</span><br><span class="line">	int res = 0, sum = 1;</span><br><span class="line">	st[x] = 1;	</span><br><span class="line">	for(int i = h[x]; i != -1; i = ne[i])&#123;</span><br><span class="line">		int j = e[i];</span><br><span class="line">		if(!st[j])&#123;</span><br><span class="line">			int s = dfs(j);</span><br><span class="line">			// 子图最大结点数 </span><br><span class="line">			res = max(res, s);</span><br><span class="line">			// j为根的节点总数 </span><br><span class="line">			sum += s;		</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	// a - sum：另一部分的节点总数 </span><br><span class="line">	res = max(res, a - sum);</span><br><span class="line">	// 选取最小的最大结点数 </span><br><span class="line">	ans = min(ans, res);</span><br><span class="line">	return sum;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">  	//初始化h数组 -1表示尾节</span><br><span class="line">	memset(h, -1, sizeof h); </span><br><span class="line">    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);</span><br><span class="line">    cin &gt;&gt; a;</span><br><span class="line">    // 创建邻接表 </span><br><span class="line">    for(int i = 0; i &lt; a - 1; i++)&#123;</span><br><span class="line">    	int m, n;</span><br><span class="line">    	cin &gt;&gt; m &gt;&gt; n;</span><br><span class="line">    	add(m, n);</span><br><span class="line">    	add(n, m);</span><br><span class="line">	&#125;</span><br><span class="line">    dfs(1);</span><br><span class="line">    cout &lt;&lt; ans &lt;&lt; endl;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="树与图的广度优先遍历"><a href="#树与图的广度优先遍历" class="headerlink" title="树与图的广度优先遍历"></a>树与图的广度优先遍历</h3><h4 id="AcWing-847-图中点的层次"><a href="#AcWing-847-图中点的层次" class="headerlink" title="AcWing 847. 图中点的层次"></a>AcWing 847. 图中点的层次</h4><p>思路：邻接表bfs</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 2e5 + 10;</span><br><span class="line"></span><br><span class="line">// 邻接表头结点 </span><br><span class="line">int h[N];</span><br><span class="line">// 存储元素 </span><br><span class="line">int e[N];</span><br><span class="line">// 下个节点值</span><br><span class="line">int ne[N];</span><br><span class="line">// 结点是否访问过</span><br><span class="line">int st[N]; </span><br><span class="line">// 单链表指针 </span><br><span class="line">int idx = 0; </span><br><span class="line">int a, b, ans = N; </span><br><span class="line"></span><br><span class="line">void add(int x, int y)&#123;</span><br><span class="line">	e[idx] = y, ne[idx] = h[x], h[x] = idx, idx ++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">void dfs(int x)&#123;</span><br><span class="line">    queue&lt;pair&lt;int, int&gt;&gt; q;</span><br><span class="line">    map&lt;pair&lt;int, int&gt;, int&gt; ump;</span><br><span class="line">    q.push(&#123;1, 1&#125;);</span><br><span class="line">    ump[&#123;1, 1&#125;] = 0;</span><br><span class="line">    while(!q.empty())&#123;</span><br><span class="line">        auto top = q.front();</span><br><span class="line">        q.pop();</span><br><span class="line">        int xx = top.first, yy = top.second;</span><br><span class="line">        if(yy == a)&#123;</span><br><span class="line">        	cout &lt;&lt; ump[&#123;xx, yy&#125;] &lt;&lt; endl;</span><br><span class="line">        	return;</span><br><span class="line">		&#125;</span><br><span class="line">		for(int i = h[yy]; i != -1; i = ne[i])&#123;</span><br><span class="line">			if(ump.find(&#123;yy, e[i]&#125;) == ump.end())&#123;</span><br><span class="line">				q.push(&#123;yy, e[i]&#125;);</span><br><span class="line">				ump[&#123;yy, e[i]&#125;] = ump[&#123;xx, yy&#125;] + 1;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">    &#125;   </span><br><span class="line">	cout &lt;&lt; -1 &lt;&lt; endl; </span><br><span class="line"> </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">  	//初始化h数组 -1表示尾节</span><br><span class="line">	memset(h, -1, sizeof h); </span><br><span class="line">    cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    // 创建邻接表 </span><br><span class="line">    for(int i = 0; i &lt; b; i++)&#123;</span><br><span class="line">    	int m, n;</span><br><span class="line">    	cin &gt;&gt; m &gt;&gt; n;</span><br><span class="line">    	add(m, n);</span><br><span class="line">	&#125;</span><br><span class="line">    dfs(1);</span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="拓扑排序"><a href="#拓扑排序" class="headerlink" title="拓扑排序"></a>拓扑排序</h3><h4 id="AcWing-848-有向图的拓扑序列"><a href="#AcWing-848-有向图的拓扑序列" class="headerlink" title="AcWing 848. 有向图的拓扑序列"></a>AcWing 848. 有向图的拓扑序列</h4><p>思路：邻接表找入度为0的结点</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line"></span><br><span class="line">int h[N], e[N], ne[N], idx, a, b;</span><br><span class="line">queue&lt;int&gt; q;</span><br><span class="line">// 保存各个点的入度</span><br><span class="line">int d[N]; </span><br><span class="line">// v存放答案</span><br><span class="line">vector&lt;int&gt; v;</span><br><span class="line"></span><br><span class="line">void add(int x, int y)&#123;</span><br><span class="line">    e[idx] = y, ne[idx] = h[x], h[x] = idx++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">bool topsort()&#123;</span><br><span class="line">    // 找出入读为0的点</span><br><span class="line">    for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">    	if(!d[i]) q.push(i); </span><br><span class="line">	&#125;	</span><br><span class="line">	while(q.size())&#123;</span><br><span class="line">		int top = q.front();</span><br><span class="line">		q.pop();</span><br><span class="line">		v.push_back(top);</span><br><span class="line">		// 每次循环减去一条边</span><br><span class="line">		for(int i = h[top]; i != -1; i = ne[i])&#123;</span><br><span class="line">			int j = e[i];</span><br><span class="line">			d[j] --;</span><br><span class="line">			// 当减去后的入读为0则入队列</span><br><span class="line">			if(!d[j]) q.push(j);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return v.size() == a;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">  	</span><br><span class="line">  	memset(h, -1, sizeof h);</span><br><span class="line">  	cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">  	while(b--)&#123;</span><br><span class="line">  	    int x, y;</span><br><span class="line">  	    cin &gt;&gt; x &gt;&gt; y;</span><br><span class="line">  	    add(x, y);</span><br><span class="line">  	    d[y] ++;</span><br><span class="line">  	&#125;</span><br><span class="line">  	if(topsort())&#123;</span><br><span class="line">  		for(int i = 0; i &lt; v.size(); i++) cout &lt;&lt; v[i] &lt;&lt; &quot; &quot;;</span><br><span class="line">	&#125;</span><br><span class="line">	else puts(&quot;-1&quot;);</span><br><span class="line">  	</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="Dijkstra"><a href="#Dijkstra" class="headerlink" title="Dijkstra"></a>Dijkstra</h3><p>稠密图：临界矩阵（点较少）<br>稀疏图：邻接表（点较多）</p>
<h4 id="AcWing-849-Dijkstra求最短路-I"><a href="#AcWing-849-Dijkstra求最短路-I" class="headerlink" title="AcWing 849. Dijkstra求最短路 I"></a>AcWing 849. Dijkstra求最短路 I</h4><p><strong>朴素版（暴力）</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"></span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line">int m, n;</span><br><span class="line">// 为稠密阵所以用邻接矩阵存储</span><br><span class="line">int num[501][501];</span><br><span class="line">// 用于记录每一个点距离第一个点的距离</span><br><span class="line">int dis[N];</span><br><span class="line">// 用于记录该点的最短距离是否已经确定</span><br><span class="line">int st[N];</span><br><span class="line"></span><br><span class="line">int dijkstra()&#123;</span><br><span class="line">	memset(dis, 0x3f3f3f3f, sizeof dis);</span><br><span class="line">	dis[1] = 0;</span><br><span class="line">	for(int i = 0; i &lt; m; i++)&#123;</span><br><span class="line">		int t = -1;</span><br><span class="line">		// 找到没有确定最短路径的节点中距离源点最近的点t </span><br><span class="line">		for(int j = 1; j &lt;= m; j++)&#123;</span><br><span class="line">			if(!st[j] &amp;&amp; (t == -1 || dis[t] &gt; dis[j]))&#123;</span><br><span class="line">				t = j;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		st[t] = 1;</span><br><span class="line">		// 更新到其他点的距离 </span><br><span class="line">		for(int k = 1; k &lt;= m; k++)&#123;</span><br><span class="line">			dis[k] = min(dis[k], dis[t] + num[t][k]);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	if(dis[m]==0x3f3f3f3f) return -1;</span><br><span class="line">    return dis[m];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	memset(num, 0x3f3f3f3f, sizeof num);</span><br><span class="line">	cin &gt;&gt; m &gt;&gt; n;</span><br><span class="line">	for(int i = 0; i &lt; n; i++)&#123;</span><br><span class="line">		int x, y, z;</span><br><span class="line">		cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;</span><br><span class="line">		num[x][y] = min(num[x][y], z);</span><br><span class="line">	&#125;</span><br><span class="line">  	cout &lt;&lt; dijkstra() &lt;&lt; endl;</span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-850-Dijkstra求最短路-II"><a href="#AcWing-850-Dijkstra求最短路-II" class="headerlink" title="AcWing 850. Dijkstra求最短路 II"></a>AcWing 850. Dijkstra求最短路 II</h4><p><strong>临界表法</strong></p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt;</span><br><span class="line"> </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e6 + 10;</span><br><span class="line">typedef pair&lt;int, int&gt; PII;</span><br><span class="line"></span><br><span class="line">int e[N], ne[N], idx, h[N], dis[N], st[N];</span><br><span class="line">int w[N]; // 存放权重 </span><br><span class="line">int a, b;</span><br><span class="line"></span><br><span class="line">void add(int x, int y, int z)&#123;</span><br><span class="line">	w[idx] = z, e[idx] = y, ne[idx] = h[x], h[x] = idx++;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int dj()&#123;</span><br><span class="line">	memset(dis, 0x3f3f3f3f, sizeof dis);</span><br><span class="line">	priority_queue&lt;PII, vector&lt;PII&gt;, greater&lt;PII&gt;&gt; heap;</span><br><span class="line">	// 插入距离和结点编号 </span><br><span class="line">	heap.push(&#123;0, 1&#125;);</span><br><span class="line">	while(!heap.empty())&#123;</span><br><span class="line">		auto top = heap.top();</span><br><span class="line">		heap.pop();</span><br><span class="line">		int x = top.second, y = top.first;</span><br><span class="line">		if(st[x]) continue;</span><br><span class="line">		st[x] = 1;</span><br><span class="line">		// 遍历该节点的每个临界结点，给每个选出最短距离 </span><br><span class="line">		for(int i = h[x]; i != -1; i = ne[i])&#123;</span><br><span class="line">			int j = e[i];</span><br><span class="line">			if(dis[j] &gt; dis[x] + w[i])&#123;</span><br><span class="line">				dis[j] = dis[x] + w[i];</span><br><span class="line">				heap.push(&#123;dis[j], j&#125;);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	if(dis[a] == 0x3f3f3f3f) return -1;</span><br><span class="line">	return dis[a];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	memset(h, -1, sizeof h);</span><br><span class="line">	cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">	while(b--)&#123;</span><br><span class="line">		int x, y, z;</span><br><span class="line">		cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;</span><br><span class="line">		add(x, y, z);</span><br><span class="line">		add(y, x, z);</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; dj() &lt;&lt; endl;</span><br><span class="line"></span><br><span class="line">    return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="Floyd"><a href="#Floyd" class="headerlink" title="Floyd"></a>Floyd</h3><p>与迪杰斯特拉的区别：</p>
<ul>
<li>迪杰斯特拉算法适用于非负权，用于查找1到n 的最短距离，数据范围大</li>
<li>弗洛伊德算法适用于含有负权，用于查找每个点之间的最短距离，数据范围较少</li>
</ul>
<h4 id="AcWing-854-Floyd求最短路"><a href="#AcWing-854-Floyd求最短路" class="headerlink" title="AcWing 854. Floyd求最短路"></a>AcWing 854. Floyd求最短路</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e6 + 10;</span><br><span class="line">const int INF = 0x3f3f3f3f;</span><br><span class="line">typedef pair&lt;int, int&gt; PII;</span><br><span class="line"></span><br><span class="line">int n, m, k;</span><br><span class="line">int e[201][201];</span><br><span class="line"></span><br><span class="line">void floyd()&#123;</span><br><span class="line">	//  f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。</span><br><span class="line">    // 因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。 </span><br><span class="line">	for(int k = 1; k &lt;= n; k++)&#123;</span><br><span class="line">		for(int i = 1; i &lt;= n; i++)&#123;</span><br><span class="line">			for(int j = 1; j &lt;= n; j++)&#123;</span><br><span class="line">				e[i][j] = min(e[i][j], e[i][k] + e[k][j]);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	cin &gt;&gt; n &gt;&gt; m &gt;&gt; k; </span><br><span class="line">	for(int i = 1; i &lt;= n; i++)&#123;</span><br><span class="line">		for(int j = 1; j &lt;= n; j++)&#123;</span><br><span class="line">			if(i == j) e[i][j] = 0;</span><br><span class="line">			else e[i][j] = INF;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	for(int i = 0; i &lt; m; i++)&#123;</span><br><span class="line">		int x, y, z;</span><br><span class="line">		cin &gt;&gt; x &gt;&gt; y &gt;&gt; z;</span><br><span class="line">		e[x][y] = min(e[x][y], z);</span><br><span class="line">	&#125;</span><br><span class="line">	floyd();</span><br><span class="line">	while(k--)&#123;</span><br><span class="line">		int x, y;</span><br><span class="line">		cin &gt;&gt; x &gt;&gt; y;</span><br><span class="line">		// 不能e[x][y] == INF，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，t大于某个与INF相同数量级的数即可 </span><br><span class="line">		if(e[x][y] &gt; INF / 2) cout &lt;&lt; &quot;impossible&quot;&lt;&lt;endl;</span><br><span class="line">		else cout &lt;&lt; e[x][y] &lt;&lt;endl;</span><br><span class="line">	&#125;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="数学知识"><a href="#数学知识" class="headerlink" title="数学知识"></a>数学知识</h2><h3 id="质数"><a href="#质数" class="headerlink" title="质数"></a>质数</h3><h4 id="AcWing-867-分解质因数"><a href="#AcWing-867-分解质因数" class="headerlink" title="AcWing 867. 分解质因数"></a>AcWing 867. 分解质因数</h4><p>主要需要开方来避免超时</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	</span><br><span class="line">	int n, m;</span><br><span class="line">	cin &gt;&gt; n;</span><br><span class="line">	while(n--)&#123;</span><br><span class="line">		cin &gt;&gt; m;</span><br><span class="line">		int mm = m, flag = 0;</span><br><span class="line">		for(int i = 2; i &lt;= m / i; i++)&#123;</span><br><span class="line">			int idx = 0;</span><br><span class="line">			while(mm % i == 0)&#123;</span><br><span class="line">				idx ++;</span><br><span class="line">				mm /= i;</span><br><span class="line">			&#125;</span><br><span class="line">			if(idx != 0)&#123;</span><br><span class="line">			    flag = 1;</span><br><span class="line">			    cout &lt;&lt; i &lt;&lt; &quot; &quot; &lt;&lt; idx &lt;&lt; endl;</span><br><span class="line">			&#125; </span><br><span class="line">		&#125;</span><br><span class="line">		if(flag)&#123;</span><br><span class="line">	        if(mm != 1) cout &lt;&lt; mm &lt;&lt; &quot; &quot; &lt;&lt; 1 &lt;&lt; endl;</span><br><span class="line">	        cout &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">		else &#123;</span><br><span class="line">		    cout &lt;&lt; m &lt;&lt; &quot; &quot; &lt;&lt; 1 &lt;&lt; endl;</span><br><span class="line">		    cout &lt;&lt; endl;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-868-筛质数"><a href="#AcWing-868-筛质数" class="headerlink" title="AcWing 868. 筛质数"></a>AcWing 868. 筛质数</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e6 + 10;</span><br><span class="line">int n[N], st[N], idx;</span><br><span class="line"></span><br><span class="line">void init()&#123;</span><br><span class="line">	for(int i = 2; i &lt;= N; i++)&#123;</span><br><span class="line">		if(!st[i]) n[idx++] = i;</span><br><span class="line">		for(int j = 0; n[j] &lt;= N / i; j++)&#123;</span><br><span class="line">			st[n[j] * i] = 1;</span><br><span class="line">			if(i % n[j] == 0) break;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	init();</span><br><span class="line">	int a, res = 0;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	for(int i = 2; i &lt;= a; i++)&#123;</span><br><span class="line">		if(!st[i])&#123;</span><br><span class="line">			res ++;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; res &lt;&lt; endl;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="约数"><a href="#约数" class="headerlink" title="约数"></a>约数</h3><p><img src="" data-original="http://www.lijunxi.site:4000/api/file/download/bd17a18c-0c3c-475c-87f2-30830d333ee3.png" alt="图片描述"></p>
<h4 id="AcWing-870-约数个数"><a href="#AcWing-870-约数个数" class="headerlink" title="AcWing 870. 约数个数"></a>AcWing 870. 约数个数</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10, M = 1e9 + 7;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	set&lt;int&gt; s;</span><br><span class="line">	map&lt;int, int&gt; mp;</span><br><span class="line">	ll a, b, res = 1;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	while(a--)&#123;</span><br><span class="line">		cin &gt;&gt; b;</span><br><span class="line">		int xx = b;</span><br><span class="line">		for(int i = 2; i &lt;= b / i; i++)&#123;</span><br><span class="line">			while(xx % i == 0)&#123;</span><br><span class="line">				xx /= i; </span><br><span class="line">				mp[i] ++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">                // x的最大公约数可能大于sqrt(x);</span><br><span class="line">		if(xx &gt; 1) mp[xx] ++;</span><br><span class="line">	&#125;</span><br><span class="line">	for(auto i: mp)&#123;</span><br><span class="line">		res = (res * (i.second + 1)) % M; </span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; res &lt;&lt; endl;</span><br><span class="line"></span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-871-约数之和"><a href="#AcWing-871-约数之和" class="headerlink" title="AcWing 871. 约数之和"></a>AcWing 871. 约数之和</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10, M = 1e9 + 7;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	map&lt;ll, ll&gt; mp;</span><br><span class="line">	int a;</span><br><span class="line">	ll res = 1;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	while(a--)&#123;</span><br><span class="line">		int m;</span><br><span class="line">		cin &gt;&gt; m;</span><br><span class="line">		int c = m;</span><br><span class="line">		for(int i = 2; i &lt;= m / i; i++)&#123;</span><br><span class="line">			ll cot = 0;</span><br><span class="line">			while(c % i == 0)&#123;</span><br><span class="line">				c /= i;</span><br><span class="line">				mp[i] ++;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		if(c &gt; 1) mp[c] ++;	</span><br><span class="line">	&#125;</span><br><span class="line">	for(auto i: mp)&#123;</span><br><span class="line">		ll x = i.first, y = i.second, cot1 = 1, cot2 = 1;</span><br><span class="line">		while(y--)&#123; </span><br><span class="line">			cot2 = cot2 * x % M;</span><br><span class="line">			cot1 = (cot1 + cot2) % M;</span><br><span class="line">		&#125;</span><br><span class="line">		res = (res * cot1) % M;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; res &lt;&lt; endl;</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-872-最大公约数"><a href="#AcWing-872-最大公约数" class="headerlink" title="AcWing 872. 最大公约数"></a>AcWing 872. 最大公约数</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10, M = 1e9 + 7;</span><br><span class="line">// 最大公约数</span><br><span class="line">ll fun1(int x, int y)&#123;</span><br><span class="line">	return y ? fun1(y, x % y) : x;</span><br><span class="line">&#125;</span><br><span class="line">// 最小公倍数</span><br><span class="line">ll fun2(int x, int y)&#123;</span><br><span class="line">	return x * fun1(x, y) / y;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	</span><br><span class="line">	int a;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	while(a--)&#123;</span><br><span class="line">		int m, n;</span><br><span class="line">		cin &gt;&gt; m &gt;&gt; n;</span><br><span class="line">		cout &lt;&lt; fun1(m, n) &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="欧拉函数"><a href="#欧拉函数" class="headerlink" title="欧拉函数"></a>欧拉函数</h3><blockquote>
<p>1∼N 中与 N 互质的数的个数被称为欧拉函数，称为O(n)<br>若N &#x3D; p1^a*p2^b*p3^c*…..<br>则O(N) &#x3D; N * (p1-1)&#x2F;p1 * (p2-1)&#x2F;p2 * (p3-1)&#x2F;p3 *…..</p>
</blockquote>
<h4 id="AcWing-873-欧拉函数"><a href="#AcWing-873-欧拉函数" class="headerlink" title="AcWing 873. 欧拉函数"></a>AcWing 873. 欧拉函数</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10, M = 1e9 + 7;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	</span><br><span class="line">	int a;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	while(a--)&#123;</span><br><span class="line">		int m;</span><br><span class="line">		cin &gt;&gt; m;</span><br><span class="line">		ll res = m; </span><br><span class="line">		map&lt;int, ll&gt; mp;</span><br><span class="line">		for(int i = 2; i &lt;= m / i; i++)&#123;</span><br><span class="line">			while(m % i == 0)&#123;</span><br><span class="line">				m /= i;</span><br><span class="line">				mp[i] ++;</span><br><span class="line">			&#125; </span><br><span class="line">		&#125;</span><br><span class="line">		if(m &gt; 1) mp[m] ++;</span><br><span class="line">		for(auto i: mp)&#123;</span><br><span class="line">			int x = i.first;</span><br><span class="line">			res = res * (x - 1) / x;</span><br><span class="line">		&#125; </span><br><span class="line">		cout &lt;&lt; res &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="组合数"><a href="#组合数" class="headerlink" title="组合数"></a>组合数</h3><h4 id="AcWing-885-求组合数-I"><a href="#AcWing-885-求组合数-I" class="headerlink" title="AcWing 885. 求组合数 I"></a>AcWing 885. 求组合数 I</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e6 + 10, M = 1e9 + 7;</span><br><span class="line"></span><br><span class="line">int e[2010][2010];</span><br><span class="line"></span><br><span class="line">void init()&#123;</span><br><span class="line">    // 类似于DP</span><br><span class="line">    // e[i][j]就代表的是Cij</span><br><span class="line">	for(int i = 0; i &lt; 2010; i++)&#123;</span><br><span class="line">		for(int j = 0; j &lt;= i; j++)&#123;</span><br><span class="line">		    // Ci0为1</span><br><span class="line">			if(!j) e[i][j] = 1;</span><br><span class="line">			else e[i][j] = (e[i-1][j-1] + e[i-1][j]) % M;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125; </span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	</span><br><span class="line">	init(); </span><br><span class="line">	int a;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	while(a--)&#123;</span><br><span class="line">		int m, n;</span><br><span class="line">		cin &gt;&gt; m &gt;&gt; n;</span><br><span class="line">		cout &lt;&lt; e[m][n] &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="容斥原理"><a href="#容斥原理" class="headerlink" title="容斥原理"></a>容斥原理</h3><h4 id="AcWing-890-能被整除的数"><a href="#AcWing-890-能被整除的数" class="headerlink" title="AcWing 890. 能被整除的数"></a>AcWing 890. 能被整除的数</h4><p>若给出的待求的数组都是互质</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">1e5</span> + <span class="number">10</span>;</span><br><span class="line"><span class="type">int</span> v[<span class="number">20</span>];</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="type">int</span> a, b, res = <span class="number">0</span>;</span><br><span class="line">    cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; b; i ++)&#123;</span><br><span class="line">        cin &gt;&gt; v[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; <span class="number">1</span> &lt;&lt; b; i ++)&#123;</span><br><span class="line">        <span class="type">int</span> cot = <span class="number">0</span>, t = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; b; j ++)&#123;</span><br><span class="line">            <span class="keyword">if</span>(i &gt;&gt; j &amp; <span class="number">1</span>)&#123;</span><br><span class="line">                cot ++;</span><br><span class="line">                <span class="keyword">if</span>((ll) t * v[j] &gt; a)&#123;</span><br><span class="line">                    t = <span class="number">-1</span>;</span><br><span class="line">                    <span class="keyword">break</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                t *= v[j];</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span>(t != <span class="number">-1</span>)&#123;</span><br><span class="line">            <span class="keyword">if</span>(cot % <span class="number">2</span> == <span class="number">0</span>)&#123;</span><br><span class="line">                res -= a / t;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                res += a / t;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    cout &lt;&lt; res &lt;&lt; endl;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>否则，修改乘积为求最小公倍数</p>
<p>参考Leetcode：<a target="_blank" rel="noopener" href="https://leetcode.cn/problems/kth-smallest-amount-with-single-denomination-combination/">单面值组合的第 K 小金额</a></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Solution</span> &#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="type">int</span> len;</span><br><span class="line">    <span class="function"><span class="type">long</span> <span class="type">long</span> <span class="title">fun</span><span class="params">(<span class="type">long</span> <span class="type">long</span> x, vector&lt;<span class="type">int</span>&gt;&amp; v)</span></span>&#123;</span><br><span class="line">        <span class="type">long</span> <span class="type">long</span> res = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt; <span class="number">1</span> &lt;&lt; len; i++)&#123;</span><br><span class="line">            <span class="type">long</span> <span class="type">long</span> cot = <span class="number">0</span>, t = <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">0</span>; j &lt; len; j++)&#123;</span><br><span class="line">                <span class="keyword">if</span>(i &gt;&gt; j &amp; <span class="number">1</span>)&#123;</span><br><span class="line">                    <span class="type">long</span> <span class="type">long</span> ccc = t / <span class="built_in">gcd</span>(t, v[j]) * v[j]; <span class="comment">//《-------------修改这里</span></span><br><span class="line">                    <span class="keyword">if</span>(ccc &gt; x)&#123;</span><br><span class="line">                        t = <span class="number">-1</span>;</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    &#125;</span><br><span class="line">                    cot ++;</span><br><span class="line">                    t = ccc;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">if</span>(t != <span class="number">-1</span>)&#123;</span><br><span class="line">                <span class="keyword">if</span>(cot % <span class="number">2</span> == <span class="number">1</span>) res += x / t;</span><br><span class="line">                <span class="keyword">else</span> res -= x / t;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="type">long</span> <span class="type">long</span> <span class="title">findKthSmallest</span><span class="params">(vector&lt;<span class="type">int</span>&gt;&amp; coins, <span class="type">int</span> k)</span> </span>&#123;</span><br><span class="line">        len = coins.<span class="built_in">size</span>();</span><br><span class="line">        <span class="type">long</span> <span class="type">long</span> l = <span class="number">1</span>, r = <span class="number">1e12</span>;</span><br><span class="line">        <span class="keyword">while</span>(l &lt; r)&#123;</span><br><span class="line">            <span class="type">long</span> <span class="type">long</span> mid = (l + r) &gt;&gt; <span class="number">1</span>;</span><br><span class="line">            <span class="keyword">if</span>(<span class="built_in">fun</span>(mid, coins) &gt;= k) r = mid;</span><br><span class="line">            <span class="keyword">else</span> l = mid + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> l;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>



<h2 id="动态规划"><a href="#动态规划" class="headerlink" title="动态规划"></a>动态规划</h2><h3 id="记忆化搜索"><a href="#记忆化搜索" class="headerlink" title="记忆化搜索"></a>记忆化搜索</h3><h4 id="AcWing-901-滑雪"><a href="#AcWing-901-滑雪" class="headerlink" title="AcWing 901. 滑雪"></a>AcWing 901. 滑雪</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">const int N = 1e5 + 10;</span><br><span class="line">int a, b;</span><br><span class="line">int n[310][310], cot[310][310];</span><br><span class="line">int ix[4] = &#123;-1,0,1,0&#125;;</span><br><span class="line">int iy[4] = &#123;0,1,0,-1&#125;;</span><br><span class="line"></span><br><span class="line">int dfs(int x, int y)&#123;</span><br><span class="line">	if(cot[x][y] != -1) return cot[x][y];</span><br><span class="line">	cot[x][y] = 1;</span><br><span class="line">	for(int i = 0; i &lt; 4; i++)&#123;</span><br><span class="line">		int xx = ix[i] + x, yy = iy[i] + y;</span><br><span class="line">		if(xx &gt;= 1 &amp;&amp; xx &lt;= a &amp;&amp; yy &gt;= 1 &amp;&amp; yy &lt;= b &amp;&amp; n[x][y] &gt; n[xx][yy])&#123;</span><br><span class="line">			cot[x][y] = max(cot[x][y], dfs(xx, yy) + 1);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	return cot[x][y];</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">    memset(cot, -1, sizeof cot);</span><br><span class="line">	cin &gt;&gt; a &gt;&gt; b;</span><br><span class="line">	for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">		for(int j = 1; j &lt;= b; j++)&#123;</span><br><span class="line">			cin &gt;&gt; n[i][j];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	int ans = 0;</span><br><span class="line">	for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">		for(int j = 1; j &lt;= b; j++)&#123;</span><br><span class="line">			ans = max(ans, dfs(i, j));</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; ans &lt;&lt; endl;</span><br><span class="line">	</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="线性DP"><a href="#线性DP" class="headerlink" title="线性DP"></a>线性DP</h3><h4 id="AcWing-898-数字三角形"><a href="#AcWing-898-数字三角形" class="headerlink" title="AcWing 898. 数字三角形"></a>AcWing 898. 数字三角形</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">typedef pair&lt;int, int&gt; PII;</span><br><span class="line">const int N = 510, M = 1e5 + 10;	</span><br><span class="line">int n[N][N]; </span><br><span class="line">int cot[N][N];</span><br><span class="line">int a;</span><br><span class="line"></span><br><span class="line">int dfs(int x, int y)&#123;</span><br><span class="line">	if(x &lt; 1 || x &gt; a || y &lt; 1 || y &gt; a) return 0;</span><br><span class="line">	if(cot[x][y] != -1) return cot[x][y];</span><br><span class="line">	int _1 = dfs(x + 1, y), _2 = dfs(x + 1, y + 1);</span><br><span class="line">	cot[x][y] = max(_1, _2) + n[x][y]; </span><br><span class="line">	return cot[x][y]; </span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line">	memset(cot, -1, sizeof cot);</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	for(int i = 1; i &lt;= a; i++)&#123;</span><br><span class="line">		for(int j = 1; j &lt;= i; j++)&#123;</span><br><span class="line">			cin &gt;&gt; n[i][j];	</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; dfs(1, 1) &lt;&lt; endl;</span><br><span class="line">	</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-896-最长上升子序列"><a href="#AcWing-896-最长上升子序列" class="headerlink" title="AcWing 896. 最长上升子序列"></a>AcWing 896. 最长上升子序列</h4><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line">#include&lt;bits/stdc++.h&gt; </span><br><span class="line">using namespace std;</span><br><span class="line">typedef long long ll;</span><br><span class="line">typedef pair&lt;int, int&gt; PII;</span><br><span class="line">const int N = 1e5 + 10, M = 1e5 + 10;</span><br><span class="line">int n[N];</span><br><span class="line">int a;</span><br><span class="line">vector&lt;int&gt; v; </span><br><span class="line"></span><br><span class="line">int main()&#123;</span><br><span class="line"></span><br><span class="line">	int a;</span><br><span class="line">	cin &gt;&gt; a;</span><br><span class="line">	for(int i = 0; i &lt; a; i++) cin &gt;&gt; n[i];</span><br><span class="line">	for(int i = 0; i &lt; a; i++)&#123;</span><br><span class="line">		if(v.empty() || n[i] &gt; v.back())&#123;</span><br><span class="line">			v.push_back(n[i]);</span><br><span class="line">		&#125;</span><br><span class="line">		else&#123;</span><br><span class="line">			*lower_bound(v.begin(), v.end(), n[i]) = n[i];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	cout &lt;&lt; v.size() &lt;&lt; endl;</span><br><span class="line">	</span><br><span class="line">	return 0;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h4 id="AcWing-897-最长公共子序列"><a href="#AcWing-897-最长公共子序列" class="headerlink" title="AcWing 897. 最长公共子序列"></a>AcWing 897. 最长公共子序列</h4><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;bits/stdc++.h&gt;</span> </span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="type">long</span> <span class="type">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; PII;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> N = <span class="number">1e5</span> + <span class="number">10</span>, M = <span class="number">1e5</span> + <span class="number">10</span>;</span><br><span class="line"></span><br><span class="line"><span class="type">char</span> n1[N], n2[N];</span><br><span class="line"><span class="comment">// n[i][j]记录前i个n1和前j个n2的公共子串的最大长度</span></span><br><span class="line"><span class="type">int</span> n[<span class="number">1010</span>][<span class="number">1010</span>];</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	</span><br><span class="line">	<span class="type">int</span> a, b;</span><br><span class="line">	cin &gt;&gt; a &gt;&gt; b &gt;&gt; n1 + <span class="number">1</span> &gt;&gt; n2 + <span class="number">1</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= a; i++)&#123;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= b; j++)&#123;</span><br><span class="line">			<span class="keyword">if</span>(n1[i] == n2[j])&#123;</span><br><span class="line">				n[i][j] = n[i<span class="number">-1</span>][j<span class="number">-1</span>] + <span class="number">1</span>;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">else</span>&#123;</span><br><span class="line">				n[i][j] = <span class="built_in">max</span>(n[i<span class="number">-1</span>][j], n[i][j<span class="number">-1</span>]);</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">1</span>; i &lt;= a; i++)&#123;</span><br><span class="line">		<span class="keyword">for</span>(<span class="type">int</span> j = <span class="number">1</span>; j &lt;= b; j++)&#123;</span><br><span class="line">			cout &lt;&lt; n[i][j] &lt;&lt; <span class="string">&quot; &quot;</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		cout &lt;&lt; endl;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	cout &lt;&lt; n[a][b] &lt;&lt; endl;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta"><i class="fas fa-circle-user fa-fw"></i>文章作者: </span><span class="post-copyright-info"><a href="http://www.lijunxi.site">Jixer</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta"><i class="fas fa-square-arrow-up-right fa-fw"></i>文章链接: </span><span class="post-copyright-info"><a href="http://www.lijunxi.site/posts/476471671/">http://www.lijunxi.site/posts/476471671/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta"><i class="fas fa-circle-exclamation fa-fw"></i>版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="http://www.lijunxi.site" target="_blank">Jixer的小屋</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E7%AE%97%E6%B3%95/">算法</a></div><div class="post_share"><div class="social-share" data-image="https://q1.qlogo.cn/g?b=qq&amp;nk=2770063826&amp;s=640" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="/pluginsSrc/butterfly-extsrc/sharejs/dist/css/share.min.css?v=1.1.3" media="print" onload="this.media='all'"><script src="/pluginsSrc/butterfly-extsrc/sharejs/dist/js/social-share.min.js?v=1.1.3" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/3993141914/" title="SpringSecurity动态权限控制"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">SpringSecurity动态权限控制</div></div></a></div><div class="next-post pull-right"><a href="/posts/2004290681/" title="HelloWorld"><div class="cover" style="background: var(--default-bg-color)"></div><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">HelloWorld</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/posts/2029624507/" title="2022年算法队选拔赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-05-09</div><div class="title">2022年算法队选拔赛</div></div></a></div><div><a href="/posts/3364565471/" title="2023年团体程序设计天梯赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-03-27</div><div class="title">2023年团体程序设计天梯赛</div></div></a></div><div><a href="/posts/1684445354/" title="Leetcode第128场双周赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-05-01</div><div class="title">Leetcode第128场双周赛</div></div></a></div><div><a href="/posts/1405472621/" title="Leetcode第396场周赛"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-05-05</div><div class="title">Leetcode第396场周赛</div></div></a></div><div><a href="/posts/3290308194/" title="Leetcode热题100"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-02-25</div><div class="title">Leetcode热题100</div></div></a></div><div><a href="/posts/92738838/" title="牛客小白月赛81"><div class="cover" style="background: var(--default-bg-color)"></div><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2024-04-09</div><div class="title">牛客小白月赛81</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="" data-original="https://q1.qlogo.cn/g?b=qq&amp;nk=2770063826&amp;s=640" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">Jixer</div><div class="author-info__description"></div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">52</div></a><a href="/tags/"><div class="headline">标签</div><div class="length-num">19</div></a><a href="/categories/"><div class="headline">分类</div><div class="length-num">7</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/2770063826"><i class="fab fa-github"></i><span>Follow Me</span></a></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>公告</span></div><div class="announcement_content"></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%BA%E7%A1%80%E7%AE%97%E6%B3%95"><span class="toc-text">基础算法</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-text">快速排序</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-785-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-text">AcWing 785. 快速排序</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E7%AC%ACk%E4%B8%AA%E6%95%B0"><span class="toc-text">第k个数</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-text">归并排序</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-787-%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-text">AcWing 787. 归并排序</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BA%8C%E5%88%86"><span class="toc-text">二分</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-789-%E6%95%B0%E7%9A%84%E8%8C%83%E5%9B%B4"><span class="toc-text">AcWing 789. 数的范围</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-790-%E6%95%B0%E7%9A%84%E4%B8%89%E6%AC%A1%E6%96%B9%E6%A0%B9"><span class="toc-text">AcWing 790. 数的三次方根</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%AB%98%E7%B2%BE%E5%BA%A6"><span class="toc-text">高精度</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-791-%E9%AB%98%E7%B2%BE%E5%BA%A6%E5%8A%A0%E6%B3%95"><span class="toc-text">AcWing 791. 高精度加法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-792-%E9%AB%98%E7%B2%BE%E5%BA%A6%E5%87%8F%E6%B3%95"><span class="toc-text">AcWing 792. 高精度减法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-793-%E9%AB%98%E7%B2%BE%E5%BA%A6%E4%B9%98%E6%B3%95"><span class="toc-text">AcWing 793. 高精度乘法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-794-%E9%AB%98%E7%B2%BE%E5%BA%A6%E9%99%A4%E6%B3%95"><span class="toc-text">AcWing 794. 高精度除法</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%89%8D%E7%BC%80%E5%92%8C%E4%B8%8E%E5%B7%AE%E5%88%86"><span class="toc-text">前缀和与差分</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-795-%E5%89%8D%E7%BC%80%E5%92%8C"><span class="toc-text">AcWing 795. 前缀和</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-796-%E5%AD%90%E7%9F%A9%E9%98%B5%E7%9A%84%E5%92%8C"><span class="toc-text">AcWing 796. 子矩阵的和</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-797-%E5%B7%AE%E5%88%86"><span class="toc-text">AcWing 797. 差分</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-798-%E5%B7%AE%E5%88%86%E7%9F%A9%E9%98%B5"><span class="toc-text">AcWing 798. 差分矩阵</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%8C%E6%8C%87%E9%92%88%E7%AE%97%E6%B3%95"><span class="toc-text">双指针算法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-799-%E6%9C%80%E9%95%BF%E8%BF%9E%E7%BB%AD%E4%B8%8D%E9%87%8D%E5%A4%8D%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-text">AcWing 799. 最长连续不重复子序列</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-800-%E6%95%B0%E7%BB%84%E5%85%83%E7%B4%A0%E7%9A%84%E7%9B%AE%E6%A0%87%E5%92%8C"><span class="toc-text">AcWing 800. 数组元素的目标和</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-2816-%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-text">AcWing 2816. 判断子序列</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BD%8D%E8%BF%90%E7%AE%97"><span class="toc-text">位运算</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-801-%E4%BA%8C%E8%BF%9B%E5%88%B6%E4%B8%AD1%E7%9A%84%E4%B8%AA%E6%95%B0"><span class="toc-text">AcWing 801. 二进制中1的个数</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%A6%BB%E6%95%A3%E5%8C%96"><span class="toc-text">离散化</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-802-%E5%8C%BA%E9%97%B4%E5%92%8C"><span class="toc-text">AcWing 802. 区间和</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6"><span class="toc-text">区间合并</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-803-%E5%8C%BA%E9%97%B4%E5%90%88%E5%B9%B6"><span class="toc-text">AcWing 803. 区间合并</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-text">数据结构</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-text">单链表</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-826-%E5%8D%95%E9%93%BE%E8%A1%A8"><span class="toc-text">AcWing 826. 单链表</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%8C%E9%93%BE%E8%A1%A8"><span class="toc-text">双链表</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A0%88"><span class="toc-text">栈</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcAcWing-3302-%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC"><span class="toc-text">AcAcWing 3302. 表达式求值</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%98%9F%E5%88%97"><span class="toc-text">队列</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-829-%E6%A8%A1%E6%8B%9F%E9%98%9F%E5%88%97"><span class="toc-text">AcWing 829. 模拟队列</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E8%B0%83%E6%A0%88"><span class="toc-text">单调栈</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-830-%E5%8D%95%E8%B0%83%E6%A0%88"><span class="toc-text">AcWing 830. 单调栈</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8D%95%E8%B0%83%E9%98%9F%E5%88%97"><span class="toc-text">单调队列</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-154-%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3"><span class="toc-text">AcWing 154. 滑动窗口</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#KMP"><span class="toc-text">KMP</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Tire"><span class="toc-text">Tire</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-835-Trie%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BB%9F%E8%AE%A1"><span class="toc-text">AcWing 835. Trie字符串统计</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-143-%E6%9C%80%E5%A4%A7%E5%BC%82%E6%88%96%E5%AF%B9"><span class="toc-text">AcWing 143. 最大异或对</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B9%B6%E6%9F%A5%E9%9B%86"><span class="toc-text">并查集</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-836-%E5%90%88%E5%B9%B6%E9%9B%86%E5%90%88"><span class="toc-text">AcWing 836. 合并集合</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%A0%86"><span class="toc-text">堆</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-838-%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="toc-text">AcWing 838. 堆排序</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%93%88%E5%B8%8C%E8%A1%A8"><span class="toc-text">哈希表</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%90%9C%E7%B4%A2%E4%B8%8E%E5%9B%BE%E8%AE%BA"><span class="toc-text">搜索与图论</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#DFS"><span class="toc-text">DFS</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-842-%E6%8E%92%E5%88%97%E6%95%B0%E5%AD%97"><span class="toc-text">AcWing 842. 排列数字</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-843-n-%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98"><span class="toc-text">AcWing 843. n-皇后问题</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#BFS"><span class="toc-text">BFS</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-844-%E8%B5%B0%E8%BF%B7%E5%AE%AB"><span class="toc-text">AcWing 844. 走迷宫</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A0%91%E4%B8%8E%E5%9B%BE%E7%9A%84%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86"><span class="toc-text">树与图的深度优先遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-846-%E6%A0%91%E7%9A%84%E9%87%8D%E5%BF%83"><span class="toc-text">AcWing 846. 树的重心</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A0%91%E4%B8%8E%E5%9B%BE%E7%9A%84%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86"><span class="toc-text">树与图的广度优先遍历</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-847-%E5%9B%BE%E4%B8%AD%E7%82%B9%E7%9A%84%E5%B1%82%E6%AC%A1"><span class="toc-text">AcWing 847. 图中点的层次</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8B%93%E6%89%91%E6%8E%92%E5%BA%8F"><span class="toc-text">拓扑排序</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-848-%E6%9C%89%E5%90%91%E5%9B%BE%E7%9A%84%E6%8B%93%E6%89%91%E5%BA%8F%E5%88%97"><span class="toc-text">AcWing 848. 有向图的拓扑序列</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Dijkstra"><span class="toc-text">Dijkstra</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-849-Dijkstra%E6%B1%82%E6%9C%80%E7%9F%AD%E8%B7%AF-I"><span class="toc-text">AcWing 849. Dijkstra求最短路 I</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-850-Dijkstra%E6%B1%82%E6%9C%80%E7%9F%AD%E8%B7%AF-II"><span class="toc-text">AcWing 850. Dijkstra求最短路 II</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Floyd"><span class="toc-text">Floyd</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-854-Floyd%E6%B1%82%E6%9C%80%E7%9F%AD%E8%B7%AF"><span class="toc-text">AcWing 854. Floyd求最短路</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%95%B0%E5%AD%A6%E7%9F%A5%E8%AF%86"><span class="toc-text">数学知识</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%B4%A8%E6%95%B0"><span class="toc-text">质数</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-867-%E5%88%86%E8%A7%A3%E8%B4%A8%E5%9B%A0%E6%95%B0"><span class="toc-text">AcWing 867. 分解质因数</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-868-%E7%AD%9B%E8%B4%A8%E6%95%B0"><span class="toc-text">AcWing 868. 筛质数</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BA%A6%E6%95%B0"><span class="toc-text">约数</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-870-%E7%BA%A6%E6%95%B0%E4%B8%AA%E6%95%B0"><span class="toc-text">AcWing 870. 约数个数</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-871-%E7%BA%A6%E6%95%B0%E4%B9%8B%E5%92%8C"><span class="toc-text">AcWing 871. 约数之和</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-872-%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0"><span class="toc-text">AcWing 872. 最大公约数</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0"><span class="toc-text">欧拉函数</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-873-%E6%AC%A7%E6%8B%89%E5%87%BD%E6%95%B0"><span class="toc-text">AcWing 873. 欧拉函数</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BB%84%E5%90%88%E6%95%B0"><span class="toc-text">组合数</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-885-%E6%B1%82%E7%BB%84%E5%90%88%E6%95%B0-I"><span class="toc-text">AcWing 885. 求组合数 I</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%AE%B9%E6%96%A5%E5%8E%9F%E7%90%86"><span class="toc-text">容斥原理</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-890-%E8%83%BD%E8%A2%AB%E6%95%B4%E9%99%A4%E7%9A%84%E6%95%B0"><span class="toc-text">AcWing 890. 能被整除的数</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92"><span class="toc-text">动态规划</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2"><span class="toc-text">记忆化搜索</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-901-%E6%BB%91%E9%9B%AA"><span class="toc-text">AcWing 901. 滑雪</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%BA%BF%E6%80%A7DP"><span class="toc-text">线性DP</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-898-%E6%95%B0%E5%AD%97%E4%B8%89%E8%A7%92%E5%BD%A2"><span class="toc-text">AcWing 898. 数字三角形</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-896-%E6%9C%80%E9%95%BF%E4%B8%8A%E5%8D%87%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-text">AcWing 896. 最长上升子序列</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#AcWing-897-%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97"><span class="toc-text">AcWing 897. 最长公共子序列</span></a></li></ol></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/2029624507/" title="2022年算法队选拔赛">2022年算法队选拔赛</a><time datetime="2024-05-09T15:00:27.000Z" title="发表于 2024-05-09 23:00:27">2024-05-09</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/1978524057/" title="牛客小白月赛84">牛客小白月赛84</a><time datetime="2024-05-08T14:40:35.000Z" title="发表于 2024-05-08 22:40:35">2024-05-08</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/131339317/" title="软件测试资料">软件测试资料</a><time datetime="2024-05-07T03:12:52.000Z" title="发表于 2024-05-07 11:12:52">2024-05-07</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/2394234105/" title="第十四届蓝桥杯B组国赛">第十四届蓝桥杯B组国赛</a><time datetime="2024-05-05T13:40:15.000Z" title="发表于 2024-05-05 21:40:15">2024-05-05</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/posts/1405472621/" title="Leetcode第396场周赛">Leetcode第396场周赛</a><time datetime="2024-05-05T03:58:25.000Z" title="发表于 2024-05-05 11:58:25">2024-05-05</time></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2024 By Jixer</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text"><a href="https://beian.miit.gov.cn/#/Integrated/index" style="color:white" target="_blank">蜀ICP备2022009955号-1</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js?v=4.13.0"></script><script src="/js/main.js?v=4.13.0"></script><script src="/pluginsSrc/@fancyapps/ui/dist/fancybox/fancybox.umd.js?v=5.0.33"></script><div class="js-pjax"></div><script src="/js/custom-fancybox-umd-min.js"></script><script src="/js/custom-busuanzi-pure-mini.js"></script><script src="/js/Valine.min.js"></script><script src="/js/custom-social-share.min.js"></script><script src="/js/custom-typed-umd-min.js"></script><script src="/js/av-min.js"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="fas fa-times"></i></button></nav><div class="is-center" id="loading-database"><i class="fas fa-spinner fa-pulse"></i><span>  数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"/></div></div><hr/><div id="local-search-results"></div><div id="local-search-stats-wrap"></div></div></div><div id="search-mask"></div><script src="/js/search/local-search.js?v=4.13.0"></script></div></div>
        <style>
            [bg-lazy] {
                background-image: none !important;
                background-color: #eee !important;
            }
        </style>
        <script>
            window.imageLazyLoadSetting = {
                isSPA: false,
                preloadRatio: 1,
                processImages: null,
            };
        </script><script>window.addEventListener("load",function(){var t=/\.(gif|jpg|jpeg|tiff|png)$/i,r=/^data:image\/[a-z]+;base64,/;Array.prototype.slice.call(document.querySelectorAll("img[data-original]")).forEach(function(a){var e=a.parentNode;"A"===e.tagName&&(e.href.match(t)||e.href.match(r))&&(e.href=a.dataset.original)})});</script><script>!function(r){r.imageLazyLoadSetting.processImages=t;var e=r.imageLazyLoadSetting.isSPA,n=r.imageLazyLoadSetting.preloadRatio||1,c=a();function a(){var t=Array.prototype.slice.call(document.querySelectorAll("img[data-original]")),e=Array.prototype.slice.call(document.querySelectorAll("[bg-lazy]"));return t.concat(e)}function t(){e&&(c=a());for(var t,o=0;o<c.length;o++)0<=(t=(t=c[o]).getBoundingClientRect()).bottom&&0<=t.left&&t.top<=(r.innerHeight*n||document.documentElement.clientHeight*n)&&function(){var t,e,n,a,i=c[o];e=function(){c=c.filter(function(t){return i!==t}),r.imageLazyLoadSetting.onImageLoaded&&r.imageLazyLoadSetting.onImageLoaded(i)},(t=i).hasAttribute("bg-lazy")?(t.removeAttribute("bg-lazy"),e&&e()):(n=new Image,a=t.getAttribute("data-original"),n.onload=function(){t.src=a,t.removeAttribute("data-original"),e&&e()},t.src!==a&&(n.src=a))}()}function i(){clearTimeout(t.tId),t.tId=setTimeout(t,500)}t(),document.addEventListener("scroll",i),r.addEventListener("resize",i),r.addEventListener("orientationchange",i)}(this);</script></body></html>